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

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

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

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

01.09.2013, 19:58. Просмотров 1563. Ответов 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++
помогите исправить программу! запускается, на файл вывода пуст... а когда раскоментирываю - не компилруется... вот код: #include...

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

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

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

Конденсация графа - C++
Найти число компонент сильной связности, вот может быть кто-нибудь реализовывал нечто подобное?

Обход графа в глубину - C++
Как сделать обход этого графа в глубину ?

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

K-связность неориентированного графа - C++
Ребят, третью неделю уже думаю, не могу решить. Нужно написать программу на с++, определяющую k-связность графа. Как я понял с...

Фундоментальные циклы графа - C++
Нужна программа на C\C++.по фундоментальным циклам графа,есть прога подобная на паскале но она у меня почемуто не работает...хотя пример...

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

МАТРИЦА РАССТОЯНИЙ ГРАФА - C++
Доброго времени суток! Помогите пожалуйста! Пытаюсь написать программу, которая находила бы матрицу расстояний по матрице смежности....

поиск центра графа - C++
Здраствуйте. нужен универсальный код поиска центра графа(вершины или двух). рисовать или вставлять граф не нужно.


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

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

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