|
Поиск в ширину. Двудольный граф
Есть такая задача:
«Разбиение на группы не знакомых»
Условие:
Имеется N человек и матрица А размера N?N. Элемент A[i,j] матрицы равен 1, если человек i знаком с человеком j (если i-ый человек знает j-ого, то считаем, что и j-ый человек знает i-ого) и элемент A[i,j] матрицы равен 0, если i-ый человек не знаком с человеком j. Можно ли разбить людей на 2 группы, чтобы в каждой группе были только незнакомые люди.
Входные данные
Входные данные находятся в файле input.in.
Первая срока содержит количество людей N.
Затем идут N строк файла, которые задают матрицу знакомств A (каждой строке матрицы соответствует отдельная строка входного файла, числа в строках разделены пробелами).
Выходные данные
Выходные данные находятся в файле output.out.
Если можно разбить людей на две группы, чтобы в каждой группе были только незнакомые люди, то первая строка файла содержит сообщение “YES”, а вторая строка содержит номера людей, которые попали в одну из групп. Числа в строке разделяются одним пробелом и упорядочены по возрастанию. Если нет, то единственная строка файла содержит сообщение “NO”.
Пример входных данных
4
0 1 0 1
1 0 1 1
0 1 0 1
1 1 1 0
Пример выходных данных
NO
или
Пример входных данных
10
0 1 0 0 1 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 1 1 0 1
0 0 1 0 0 1 0 0 1 0
1 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 1 0 1
0 0 1 0 0 0 0 0 1 0
0 0 1 0 0 1 0 0 1 0
0 0 0 1 0 0 1 1 0 0
0 0 1 0 0 1 0 0 0 0
Пример выходных данных
YES
1 3 6 9
это надо до этого вторника сделать. бля, тока вот спать ложился и вспонимл... дурень, сроки перепутал...выручите меня кто шарит. надо на С++
задача сводится к определению того, двудольный граф это, или нет (например, определяете это поиском в ширину). Если двудольный граф, то ответ "да". и немного попотеть.
пример входных данных должен находиться в вышеименнованом файле.
вот, что успел накидать каркас:
#include "stdafx.h"
#include <fstream>
#include <iostream>
using namespace std;
int main(){
int row,col;
ifstream InFile("input.in");
if (!InFile){
cout << endl << "Error !";
}
InFile >> row; // считываем размер массива
const long n=10;
long int A[n][n];
for(int i = 0; i < row; i++){
for (int j = 0; j < row; j++){
InFile >> A[i][j];
}
}
InFile.close();
for (int i = 0; i < row; i++){
for (int j = 0; j < row; j++){
cout << A[i][j] << "\t";
}
cout << "\n";
}
//================================
//тут алгоритм или еще что))
//================================
ofstream OutFile("output.out");
if(!OutFile){
cout << "Ошибка в файле!\n";
}
OutFile << "NO";
OutFile.close();
return 0;
}
|
Линейный вид
