Untitled

Map Coloring


We consider a geographical map with N countries numbered from 1 to N (1 <= N <=  1000). For every country we know the numbers of other countries which are connected with its border. From every country we can reach to any other one, eventually crossing some borders. Write a program which determines whether it is possible to color the map only in two colors-red and blue in such a way that if two countries are connected their colors are different. The color of the first country is red. Your program must output one possible coloring for the other countries, or show, that such coloring is impossible.
[Input]
The first line is the total number of test cases T. 
A test case has two lines. In each test case, the first line has N (the number of countries) and E (the number of border) separated by a space. The next line enumerates E border. A border consists of the two countries it connects. For example, the border connecting countries 5 and 28 is represented by “5 28” or “28 5”. The indices of countries are 1 through N. All adjacent numbers in a line are each separated by a space. 
[Output]
Output the each answer in 1 line. Each line starts with ‘#x’, where x means the index of a test case, and puts a space, and prints the answer. 
If the coloring is possible, this answer must contain a list of zeros and ones, without any separators between them. The i-th digit in this sequence is the color of the i-th country. 0 corresponds to red color, and one - to blue color. If a coloring is not possible, output the integer −1.
 
[I/O Example]
Input 
1                                ← Total test case T
3 2                              ← Starting test case 1
1 2 2 3
 
Output
#1 010
 



Code:
#include<iostream>
#define max 1000
using namespace std;
int n,m;
int a[1000][1000];
int queue[1000];
int kqua[1000];
int front = -1;
int	rear = -1;

void pushq(int x){
	if(rear == max-1) rear =-1;
	rear++;
	queue[rear]=x;
	
}

int pop(){
	if(front == max-1) front =-1;
	front++;
	return queue[front];
}

bool IsEmpty(){
	if(front == rear)return true;
	else return false;
}

bool BFS(){
	for(int i=1; i<=n; i++)
	{
		front=rear=-1;
		if(kqua[i] == -1){
			kqua[i] = 0;
		}
		pushq(i);
	

		while(!IsEmpty()){
			int temp;
			temp=pop();
		
			for(int k=1; k<=n; k++){
				if(a[temp][k] == 1 && kqua[k] == kqua[temp] && kqua[k]!=-1 && kqua[temp]!=-1){ //neu ke nhau ma trung mau thi false
					return false;
				}
				if(a[temp][k] == 1 && kqua[k] ==-1){ // neu ke nhau va chua co mau thi to mau
					kqua[k] = 1-kqua[temp];
					pushq(k);
				}
				
			}
		}
	}
	return true;
}


int main(){
	//freopen("Text.txt", "r", stdin);
	int test;
	cin >> test;
	for(int tc=1; tc <=test; tc++){

		cin >> n;
		cin >> m;
	
		for (int i=1; i<=n; i++){
			for (int j=1; j<=n; j++){
				a[i][j]=0;
			}
		}
		for (int i=0; i<1000; i++){
			kqua[i] = -1;}
		int u,v;

		for (int i=1; i<=m; i++){
			cin >> u >> v;
			a[u][v]=1;
			a[v][u]=1;
		}
		
		cout << "#" << tc<<" ";
		if(BFS()){
			
			for (int i=1; i<=n; i++){
				cout << kqua[i];
			}
			cout<< endl;
		}
		else cout << -1 <<endl;
			

	}
	return 0;
}