Untitled
unknown
plain_text
a year ago
2.5 kB
2
Indexable
Never
package MapColoring; import java.io.FileInputStream; import java.io.PrintStream; import java.util.Scanner; /** * Solution */ public class Solution { static int N,E,f,r; static int[] U,V,Q,visited; static boolean check; public static void main(String[] args) throws Exception { System.setIn(new FileInputStream("input.txt")); System.setOut(new PrintStream("output.txt")); Scanner sc = new Scanner(System.in); int tc = sc.nextInt(); for(int t=1;t<=tc;t++){ N = sc.nextInt(); E = sc.nextInt(); U = new int[E]; V = new int[E]; Q = new int[N]; visited = new int[N+1]; for(int i=0;i<E;i++){ U[i] = sc.nextInt(); V[i] = sc.nextInt(); } check = true; for(int i=1;i<=N;i++){ if(visited[i]==0){ BFS(i); if(!check) break; } } System.out.print("#"+t+" "); if(!check){ System.out.print(-1); } else{ for(int i=1;i<=N;i++){ System.out.print(1-visited[i]%2); } } System.out.println(); } } static void BFS(int x){ f = 0; r = 0; Q[r++] = x; visited[x] = 1; while(f<r){ int p = Q[f++]; for(int i = 0;i<E;i++){ if(U[i]==p){ if(visited[V[i]]==0){ Q[r++] = V[i]; visited[V[i]] = visited[p]+1; } else { if(visited[V[i]]%2==visited[p]%2){ check = false; return; } } } else if(V[i]==p){ if(visited[U[i]]==0){ Q[r++] = U[i]; visited[U[i]] = visited[p]+1; } else { if(visited[U[i]]%2==visited[p]%2){ check = false; return; } } } } } } }