Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 28, средняя оценка - 4.71
Алёнка123
Сообщений: n/a
#1

Графы через списки смежности: вывести все вершины, не смежные с данной - C++

12.01.2013, 04:18. Просмотров 3808. Ответов 1
Метки нет (Все метки)

вывести на экран все вершины не смежные с данной.
код работает, но нужно еще вывести на экран:"все смежные", в случае если все вершины смежны с данной.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<fstream>
#include<stdio.h>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
 
using namespace std;
 
ifstream in("input.txt");
ofstream out("output.txt");
 
 
int main()
{ 
    int n, m, k;
    //vector<vector<int> >g(n); //Создаем список смежности
    if (in.peek() != EOF)
    {
        in >> n >> m >> k;
        vector<vector<int> >g(n);
        k--;
        g.resize(n);// изменить размер graph'а на количество вершин n:
        for (int i = 0; i < m; i++)    
        {
            int a, b;
            in >> a >> b;
            a--, b--;
            g[a].push_back(b); //Заполняем список смежности
            g[b].push_back(a); //добавлять рёбра
        }
        
        for (int i = 0; i < g.size(); i++) //Идем по вершинам графа
        {
            bool flag = false; //Создаем флаг, отвечающий за смежность с вершиной k
            
            for (int j = 0; j < g[i].size(); j++)
            {
                if (g[i][j] == k || i == k) //Если i-тая вершина имеет в соседях вершину k или сама является ей
                    flag = true //То обозначаем, что эту вершину мы не учитываем
            }
               
                if (!flag) //Если вершина не связана с вершиной к, то выводим её
                out << i + 1 << " ";
            
        }
        
    }
    in.close();
    out.close();
    return 0;
}
Добавлено через 5 часов 0 минут
Помогите, пожалуйста, доделать задачу....заранее премного благодарна)
что нужно добавить в код, чтобы он мне выводил, что все вершины смежные...?
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.01.2013, 04:18
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Графы через списки смежности: вывести все вершины, не смежные с данной (C++):

Вывести на экран вершины орграфа, смежные с данной - C++
Вывести на экран те вершины орграфа, смежные с данной, т.е. вывести &quot;входящие&quot; и &quot;выходящие&quot; соседние вершины, но моя программа выводит...

Вывести на экран вершины орграфа, смежные с данной - C++
Уффф, к завтрашнему дню нужно сдать эти задачи, помогите пожалуйста кто чем сможет :sorry: (следующие задачи через обходы в глубину и...

Не смежные вершины матрицы - C++
Найти все не смежные вершины матрицы смежности.

Графы, представление через списки - C++
Господа, выручайте. В программе реализуется граф, создаются и добавляют вершины и рёбра. Никаких проблем не было, пока не возникло...

Графы, матрица смежности, поиск петель - C++
Добрый вечер! Задача: Задан граф в виде количества вершин n≤10 и последовательности ребер (каждое ребро задается парой смежных вершин)....

Графы. Гамильтонов Цикл. Матрица смежности - C++
Вот программа, которую я взял с поиска. Программа должна найти Гамильтонов цикл. #include &lt;iostream.h&gt; #include &lt;stdlib.h&gt; const...

1
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
12.01.2013, 06:21 #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<fstream>
#include<stdio.h>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
 
using namespace std;
 
ifstream in("input.txt");
ofstream out("output.txt");
 
 
int main()
{ 
    int n, m, k, tmp=0;
    //vector<vector<int> >g(n); //Создаем список смежности
    if (in.peek() != EOF)
    {
        in >> n >> m >> k;
        vector<vector<int> >g(n);
        k--;
        g.resize(n);// изменить размер graph'а на количество вершин n:
        for (int i = 0; i < m; i++)    
        {
            int a, b;
            in >> a >> b;
            a--, b--;
            g[a].push_back(b); //Заполняем список смежности
            g[b].push_back(a); //добавлять рёбра
        }
        
        for (int i = 0; i < g.size(); i++) //Идем по вершинам графа
        {
            bool flag = false; //Создаем флаг, отвечающий за смежность с вершиной k
            
            for (int j = 0; j < g[i].size(); j++)
            {
                if (g[i][j] == k || i == k) //Если i-тая вершина имеет в соседях вершину k или сама является ей
                    flag = true //То обозначаем, что эту вершину мы не учитываем
            }
               
                if (!flag) //Если вершина не связана с вершиной к, то выводим её
                out << i + 1 << " ";
                else
                    tmp++;            
        }
        if(tmp==n)
            cout<<"YES"<<endl;
        
    }
    in.close();
    out.close();
    return 0;
}
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.01.2013, 06:21
Привет! Вот еще темы с ответами:

Вывести все возможные комбинации цепочек в матрице смежности - C++
Есть матрица смежности вида: AB0 BCD DD0 CKN NE0 KB0 Т.е. если в конце строки 0, то из одного узла есть связь только к одному...

Графы, алгоритм Диница (реализовать граф списком смежности) - C++
У меня есть готовая программа по алгоритму Диница, но граф в матричном представлении. Очень нужно чтобы кто-нибудь помог реализовать граф...

Вывести все вершины двоичного дерева - C++
Двоичное дерево задано в виде: m,g],s,y]] Как с помощью стека вывести это на экран? Набросайте, кому не трудно алгоритм) просто...

Графы,исключение из пути определённых вершины - C++
Ребят!Есть программа:программа находит кратчайший путь в графе из точки а в точку б. Так вот как будет выглядеть функция которая будет...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru