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

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

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

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

01.09.2013, 19:58. Просмотров 1464. Ответов 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;
}
Собственно хочу узнать почему он не работает
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.09.2013, 19:58     Проверка графа на двудольность
Посмотрите здесь:

построение графа C++
C++ Проверка графа на возможность достижимости одной вершины из другой
C++ Центр графа
Построение графа C++
C++ Конденсация графа
C++ Импорт графа из файла
Для графа определить его двудольность и вывести обе доли (исправить программу) C++
C++ Периферия графа
C++ Проверка на двудольность
C++ Построение графа
C++ Подобие графа
Проверка на связанность графа C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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