Untitled
unknown
java
a year ago
1.9 kB
5
Indexable
import java.util.*; import java.io.*; public class countingRoom { public static void main(String args[]) throws IOException { BufferedReader nav = new BufferedReader(new InputStreamReader(System.in)); String s = nav.readLine(); String a[] = s.split(" "); int n = Integer.parseInt(a[0]); int m = Integer.parseInt(a[1]); List<List<Integer>> li = new ArrayList<>(); for (int i = 0; i <= n; i++) { li.add(new ArrayList<>()); } for (int i = 0; i < m; i++) { String st = nav.readLine(); String aa[] = st.split(" "); int v = Integer.parseInt(aa[0]); int u = Integer.parseInt(aa[1]); li.get(v).add(u); li.get(u).add(v); } boolean[] vis = new boolean[n + 1]; boolean mark[] = new boolean[n + 1]; boolean flag[] = new boolean[1]; for (int i = 1; i <= n; i++) { if (!vis[i]) { dfs(i, vis, li, mark, true, flag); } } if (flag[0] == true) System.out.println("IMPOSSIBLE"); else { StringBuilder sb = new StringBuilder(); for (int i = 1; i <= n; i++) { if (mark[i]) sb.append(1 + " "); else sb.append(2 + " "); } System.out.println(sb.toString()); } } public static void dfs(int idx, boolean vis[], List<List<Integer>> li, boolean m[], boolean k, boolean flag[]) { vis[idx] = true; m[idx] = k; for (int i : li.get(idx)) { if (!vis[i]) { dfs(i, vis, li, m, !k, flag); } else { if (m[idx] == m[i]) flag[0] = true; } } } }
Editor is loading...
Leave a Comment