Untitled
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; } }