Untitled
unknown
plain_text
6 months ago
1.9 kB
1
Indexable
Never
#include<iostream> #define SIZE 100000 class Stack{ public: int top; int stack[SIZE]; Stack(){ this->top=-1; this->stack[SIZE]; }; bool isEmpty(){ if(top==-1){ return true; } else return false; } bool isFull(){ if(top==SIZE-1) return true; else return false; } void reset(){ top=-1; } void push(int x){ if(this->isFull()==false){ top++; stack[top]=x; } } int pop(){ if(this->isEmpty()==false){ return stack[top--]; } } int peek(){ if(this->isEmpty()==false){ return stack[top]; } } int lengthStack(){ return top+1; } }; using namespace std; int n,e; int listConnect[1010][1010]; int visit[1010]={}; Stack array; void reset(){ for(int i=0;i<1010;i++){ for(int j=0;j<1010;j++){ listConnect[i][j]=0; } visit[i]=-1; array.reset(); } } bool DFS(){ array.push(1); int color = 0; visit[1]=color; while(!array.isEmpty()){ int i=array.pop(); if(visit[i]==0){ color = 1; } else{ color = 0; }; int numConnect=listConnect[i][0]; for(int j=1;j<=numConnect;j++){ if(visit[listConnect[i][j]]!=-1){ if(visit[listConnect[i][j]]!=color) return false; continue; } visit[listConnect[i][j]]=color; array.push(listConnect[i][j]); } } return true; } int main(){ freopen("input.txt","r",stdin); int T; cin>>T; for(int tc=1;tc<=T;tc++){ //reset reset(); //input cin>>n>>e; for(int i=0;i<e;i++){ int c1,c2; cin>>c1>>c2; listConnect[c1][0]++; listConnect[c1][listConnect[c1][0]]=c2; listConnect[c2][0]++; listConnect[c2][listConnect[c2][0]]=c1; } //function //output int result=-1; if(DFS()){ cout<<"#"<<tc<<" "; for(int i=1;i<=n;i++){ cout<<visit[i]; } cout<<endl; } else{ cout<<"#"<<tc<<" "<<result<<endl; } } return 0; }