Untitled

 avatar
unknown
plain_text
2 years ago
2.3 kB
4
Indexable
// In Practice, You should use the statndard input/output
// in order to receive a score properly.
// Do not use file input and output. Please be very careful. 

#include <stdio.h>
#include <iostream>

using namespace std;
#define size 1000
int stack[size];
int top=-1;
int N,M;
int arr[size][size];
int visit[size];

void reset(){                                 //reset mang
	for (int i =0; i< size; i++) visit[i] = -1;
	int c = 0;
	for(int i=0; i<size;i++){
		for(int j=0; j<size; j++){
			arr[i][j]=0;
		}
	}
	int d = 0;
}


void push(int x){
	top++;
	stack[top]=x;
}
int pop(){
	int x=stack[top];
	top--;
	return x;
}
bool isEmpty(){
	return top==-1;
}

bool dfs(){
	push(1);
	int color=0;
	visit[1]=color;
	while (!isEmpty())
	{
		int i=pop();
		if(visit[i]==0) color =1;
		else color=0;
		int num = arr[i][0];
		for(int j=1; j<= num; j++){
			if(visit[arr[i][j]]!=- 1){
				if( visit[arr[i][j]]!=color) return false;
				continue;
			}
			visit[arr[i][j]]=color;
			push(arr[i][j]);
		}
	}
	return true;
}

int main()
{
	int tc, T;

	// The freopen function below opens input.txt file in read only mode, and afterward,
	// the program will read from input.txt file instead of standard(keyboard) input.
	// To test your program, you may save input data in input.txt file,
	// and use freopen function to read from the file when using cin function.
	// You may remove the comment symbols(//) in the below statement and use it.
	// Use #include<cstdio> or #include<stdio.h> to use the function in your program.
	// But before submission, you must remove the freopen function or rewrite comment symbols(//).

	freopen("text.txt", "r", stdin);

	cin >> T;
	for(tc = 1; tc <= T; tc++)
	{
		/**********************************
		*  Implement your algorithm here. *
		***********************************/
		int a;
		int b;
		cin>>N>>M;
		reset();
		for (int i = 0; i < M; i++)
		{
			cin>>a>>b;
			arr[a][0]++;
			arr[a][arr[a][0]]=b;
			arr[b][0]++;
			arr[b][arr[b][0]]=a;

		}
		int ans=-1;
		cout<<"#"<<tc<<" ";
		if(dfs()){
			for(int i=1; i<=N;i++){
				cout<<visit[i];
			} }
		else  cout<<ans;
		cout<<endl;
	}

	return 0;//Your program should return 0 on normal termination.
}
Editor is loading...