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

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

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

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

12.01.2013, 04:18. Просмотров 3577. Ответов 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++ Вывести все возможные комбинации цепочек в матрице смежности
C++ Графы. Гамильтонов Цикл. Матрица смежности
C++ Графы,исключение из пути определённых вершины
C++ Дана матрица смежности и неориентированный граф. Выяснить соседствуют ли две вершины с данными номерами с одной общей вершиной
C++ Задача на графы. Удалить ребро, соединяющее вершины a и b
Графы, представление через списки C++
C++ Вывести на экран вершины орграфа, смежные с данной
Вывести на экран вершины орграфа, смежные с данной C++
C++ Вывести все вершины двоичного дерева
C++ Графы, матрица смежности, поиск петель
C++ Графы, алгоритм Диница (реализовать граф списком смежности)

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4661 / 2487 / 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     Графы через списки смежности: вывести все вершины, не смежные с данной
Ответ Создать тему
Опции темы

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