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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.64
Brat_OK
0 / 0 / 0
Регистрация: 01.09.2013
Сообщений: 20
#1

Проверка графа на двудольность - C++

01.09.2013, 19:58. Просмотров 1635. Ответов 0
Метки нет (Все метки)

Есть вот такая вот задача
Во время контрольной работы профессор Флойд заметил, что некоторые студенты обмениваются записками. Сначала он хотел поставить им всем двойки, но в тот день профессор был добрым, а потому решил разделить студентов на две группы: списывающих и дающих списывать, и поставить двойки только первым.

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

Входные данные

В первой строке находятся два числа N и M - количество студентов и количество пар студентов, обменивающихся записками (1N100, 0M2N(N−1)). Далее в M строках расположены описания пар студентов: два числа, соответствующие номерам студентов, обменивающихся записками (нумерация студентов идёт с 1). Каждая пара студентов перечислена не более одного раза.

Выходные данные

Необходимо вывести ответ на задачу профессора Флойда. Если возможно разделить студентов на две группы - выведите YES; иначе выведите NO.

Примеры

Входные данные Выходные данные
--------------------------------
3 2 YES
1 2
2 3
--------------------------------
3 3 NO
1 2
2 3
1 3
--------------------------------

Прочитав задачу можно понять, что нужно реализовать dfs с проверкой на двудольность.

Вот мой код который на все запросы выводит
NO
=============================================
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
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <vector>
 
 
using namespace std;
 
int color[10000], g[1000][1000];
bool fail = false;
 
void dfs (int v, int c)
    {
        color[v] = c;
 
        for (int i = 0; i < v; i++)
            {
                if (color[i] == 0 && g[v][i] == 1)
                    {
                        dfs(i, 3-c);
                    }
                if (color[i] == c)
                    fail = true;
            }
    }
 
int main()
{
 
 
    int n, m, x, y;
 
    cin >> n >> m;
 
    for (int i = 0; i < m; i++)
        {
            cin >> x >> y;
            g[x-1][y-1] = 1;
            g[y-1][x-1] = 1;
        }
    for (int i = 0; i < n ; i++)
        {
            if (color[i] == 0)
                dfs(i, 1);
        }
 
    if (fail)
        cout << "NO";
    else
        cout << "YES";
 
    return 0;
}
Собственно хочу узнать почему он не работает
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.09.2013, 19:58
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Проверка графа на двудольность (C++):

Для графа определить его двудольность и вывести обе доли (исправить программу) - C++
помогите исправить программу! запускается, на файл вывода пуст... а когда раскоментирываю - не компилруется... вот код: #include...

Проверка на двудольность - C++
Граф является двудольным,если у него нет циклов нечетной длины,проще говоря если мы раскрасим стартовую вершинку,например,в...

Проверка на связанность графа - C++
Всем Привет. Я получил задание проверить связанный ли граф , у меня имеется матрица смежности (adjacency matri) ,а также написаны и...

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

заданно матрицу смежности простого графа. Построить каркас этого графа с использованием поиска вширь - C++
Задание: заданно матрицу смежности простого графа. Построить каркас этого графа с использованием поиска вширь. Помогите написать...

Проверка графа, заданного матрицей смежности, на двудольность - C++/CLI WinForms
Здравствуйте!!! Подскажите пожалуйста алгоритм, с помощью которого можно проверить граф, заданный матрицей смежности, на двудольность....

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.09.2013, 19:58
Привет! Вот еще темы с ответами:

Двудольность графа - C++ Builder
Требуется проверить граф на двудольность методом поиска в глубину либо в ширину на С++ Опишите, пожалуйста, алгоритм по шагам

проверка графа на связность - Pascal ABC
помогитте написать программу проверяющую граф на связность. граф задаётся в текстовом файле в виде матрици инциденции(инцидентности). ...

Проверка на связность графа - C (СИ)
Здравствуйте, помогите пожалуйста. Есть неориентированный граф. Представлен граф список смежности. Нужно проверить является ли граф связным...

Проверка графа на связность - C (СИ)
Требуется проверить граф на связность. Помогите найти ошибки. #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;locale.h&gt; ...


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

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

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