Untitled

 avatar
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