Untitled

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

int QX[100001],QY[100001];
int rear,front;
int n,m,startx, starty;
int array[1001][1001];
int visit[1001];
int visit_check[1001];
int X[1000001],Y[1000001];
int QG[1001],flag;

void reset (){
	for(int i = 0; i <= n ; i++){
		QG[i] = -1;
		for(int j = 0; j <= n; j++){
			visit[j] = 0;
			array[i][j] = 0;
		}
	}
}

int BFS (int x){
	rear = front = 0;
	QX[rear] = x;
	rear ++;
	QG[x] = 0;
	while(rear != front){
		int temx = QX[front];
		front ++;
		for(int i = 1; i <= n; i++){
			if(array[temx][i] == 1 && QG[i] == -1){
				if(QG[temx] == 0){
					QG[i] = 1;
				}
				else {
					QG[i] = 0;
				}
				QX[rear] = i;
				rear++;
			}
			else if (array[temx][i] == 1 && QG[temx] == QG[i]) return 0;
		}
	}
	return 1;
}
int main(){
	//freopen("Text.txt","r",stdin);
	int T; cin >> T;
	for(int tc = 1; tc <= T; tc ++){
		cin >> n >> m ;
		reset();
		for(int i = 0; i < m; i++){
			int a,b;
			cin >> a >> b;
			array[a][b] = 1;
			array[b][a] = 1;
			if(i == 0){
				startx = a;
				QG[a] = 0; // danh dau quoc gia dau tien mau do
			}
		}
		if(BFS(startx) == 1){
			cout << "#" << tc << " ";
			for(int i = 1; i <= n; i++){
				cout << QG[i];
			}
			cout << endl;
		}
		else cout << "#" << tc << " " << -1 << endl;
	}
	return 0;
}