Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.4 kB
6
Indexable
Never
#include <iostream>
#include <fstream>
using namespace std;

int n, e;
int arr[1001][1001];
int visited[1001];
int color[1001];
int ans[1001];
int c;

typedef struct Point {
	int x, y;
};

Point E[10001];

void DFS(int i) {
	for (int j = 1; j <= n; j++) {
		if (arr[i][j] == 1 && visited[j] == 0) {
			visited[j] = 1;
			color[j] = 1 - color[i];
			ans[c++] = j;
			DFS(j);
		}
	}
}

void reset() {
	for (int i = 1; i <= n; i++) {
		visited[i] = 0;
		color[i] = 0;
		ans[i] = 0;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			arr[i][j] = 0;
		}
	}
}

int main() {
	ifstream input("input.txt");
	fstream output;
	output.open("output.txt");

	int t;
	input >> t;
	for (int tc = 1; tc <= t; tc++) {
		input >> n >> e;
		reset();
		int p, q;
		for (int i = 1; i <= e; i++) {
			input >> p >> q;
			E[i].x = p;
			E[i].y = q;
			arr[p][q] = 1;
			arr[q][p] = 1;
		}

		visited[1] = 1;
		color[1] = 0;
		ans[1] = 1;
		c = 2;
		DFS(1);

		bool flag = true;

		for (int i = 1; i <= e; i++) {
			if (color[E[i].x] == color[E[i].y]) {
				flag = false;
				break;
			}
		}

		output << "#" << tc << " ";

		//output << n << " " << c - 1 << endl;

		if (!flag)
			output << "-1";
		else {
			for (int i = 1; i <= n; i++)
				output << color[i];
		}

		output << endl;
	}
}