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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Объявление переменных в классе http://www.cyberforum.ru/cpp-beginners/thread946853.html
#pragma once class streetdb { public: streetdb(void); ~streetdb(void); int admiral_1_137; private: };
C++ Должен ли вызываться деструктор при создании? есть класс с конструктором и деструктором #ifndef PROCESSOR_H #define PROCESSOR_H #include "Problem.h" #include <list> using namespace std; class Processor http://www.cyberforum.ru/cpp-beginners/thread946840.html
Перемещение каретки в указанные координаты C++
Доброе время суток, Подскажите как сдвинуть каретку в консоле на заданные координаты
C++ перегруженный конструктор
можно пример перегруженного конструктора ?)
C++ Не могу удалить таблицы в БД SQLite http://www.cyberforum.ru/cpp-beginners/thread946814.html
К программе подключена либа SQLite для реализации небольшого хранилища данных. Иногда это хранилище надо очищать. Так вот, я столкнулся с проблемой удаления таблиц из базы: после выполнения DROP TABLE IF EXISTS 'table' таблица как была, так и остается в базе. Уже ознакомился с VACUUM и режимом aut_vacuum: пробовал и то, и другое - ничего не помогает. Также пробовал стереть данные из таблицы...
C++ Удаление переменных из памаяти Как удалить переменную (в классе) созданную не через new или она автамfтически удалиться при вызове delete для объекта? подробнее

Показать сообщение отдельно
Brat_OK
0 / 0 / 0
Регистрация: 01.09.2013
Сообщений: 20

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

01.09.2013, 19:58. Просмотров 1537. Ответов 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;
}
Собственно хочу узнать почему он не работает
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru