Untitled
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...