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

графы через списки смежности - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 28, средняя оценка - 4.71
Алёнка123
Сообщений: n/a
12.01.2013, 04:18     графы через списки смежности #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     графы через списки смежности
Посмотрите здесь:

Графы. Проехать из A в B через C. C++
C++ Массивы, списки, деревья, графы - для новичка)
C++ Графы. Гамильтонов Цикл. Матрица смежности
C++ список смежности в матрицу смежности
C++ Матрица смежности, ввод через рёбра
Графы, представление через списки C++
Списки, как склеить списки между собой? C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 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;
}
Yandex
Объявления
12.01.2013, 06:21     графы через списки смежности
Ответ Создать тему
Опции темы

Текущее время: 02:05. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru