Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.88/32: Рейтинг темы: голосов - 32, средняя оценка - 4.88
Алёнка123
1

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

12.01.2013, 04:18. Просмотров 5865. Ответов 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 минут
Помогите, пожалуйста, доделать задачу....заранее премного благодарна)
что нужно добавить в код, чтобы он мне выводил, что все вершины смежные...?
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
12.01.2013, 04:18
Ответы с готовыми решениями:

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

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

Реализация графа через смежные вершины
Здравствуйте. У меня есть задача- написать функции для графа через сопредельные вершины - добавить...

Раскрасить вершины графа, чтобы смежные вершины были окрашены в различные цвета
Добрый день. Прошу вашей помощи от безысходности. 4 дня назад выдана задача, которую требуется...

1
Эксперт С++
4710 / 2535 / 753
Регистрация: 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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.01.2013, 06:21

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь или здесь.

Определить смежные вершины к вершине Е в графе, заданном матрицей смежности
Определить смежные вершины к вершине Е в графе, заданном матрицей смежности: ***** A B C D E A 0...

Для данной вершины орграфа вывести на экран все «выходящие» соседние вершины
Ребят, помогите пожалуйста сделать задачку на шарпе. Задание: Для данной вершины орграфа вывести на...

Графы. Найти все вершины заданного графа, недостижимые от заданной его вершины
Найти все вершины заданного графа, недостижимые от заданной его вершины. Помогите решить...

Ориентированный граф через списки смежности
Повторяю для себя очевидные вещи, перевожу с C++ на Дельфи, но тень сомнения затмила мой разум)...


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

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

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