[백준][1707번] 이분 그래프

문제 URL

https://www.acmicpc.net/problem/1707

풀이 1

• check는 다음과 같은 수를 저장한다. 0: 방문안함 1 : 그룹번호 2 : 그룹번호
• dfs를 이용해 check변수에 그룹번호를 저장한다. 탐색할떄마다 그룹번호는 번갈아가면서 저장한다. (1,2,1,2,1,2 …)
• dfs를 마쳤으면 인접리스트를 통해서 각 정점마다 연결된 간선들을 순회하며 같은 그룹에 속해있는지를 확인한다.

import java.util.*;

public class Main {
    public static void dfs(ArrayList<Integer>[] a, int[] color, int x, int c) {
        color[x] = c;
        for (int y : a[x]) {
            if (color[y] == 0) {
                dfs(a, color, y, 3-c);
            }
        }
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            ArrayList<Integer>[] a = (ArrayList<Integer>[]) new ArrayList[n+1];
            for (int i=1; i<=n; i++) {
                a[i] = new ArrayList<Integer>();
            }
            for (int i=0; i<m; i++) {
                int u = sc.nextInt();
                int v = sc.nextInt();
                a[u].add(v);
                a[v].add(u);
            }
            int[] color = new int[n+1];
            boolean ok = true;
            for (int i=1; i<=n; i++) {
                if (color[i] == 0) {
                    dfs(a, color, i, 1);
                }
            }
            for (int i=1; i<=n; i++) {
                for (int j : a[i]) {
                    if (color[i] == color[j]) {
                        ok = false;
                    }
                }
            }
            if (ok) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }

    }
}

풀이2

(1) 이분그래프면 true 아니면 false 반환 (2) 방문안했으면 해당 정점 dfs 탐색 이어나간다. (3) 방문했지만

import java.util.*;

public class Main {
  //(1)
    public static boolean dfs(ArrayList<Integer>[] a, int[] color, int x, int c) {
        color[x] = c;
        for (int y : a[x]) {
          //(2)
            if (color[y] == 0) {
                if (dfs(a, color, y, 3-c) == false) {
                    return false;
                }
            //(3)  
            } else if (color[y] == color[x]) {
                return false;
            }
        }
        return true;
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            ArrayList<Integer>[] a = (ArrayList<Integer>[]) new ArrayList[n+1];
            for (int i=1; i<=n; i++) {
                a[i] = new ArrayList<Integer>();
            }
            for (int i=0; i<m; i++) {
                int u = sc.nextInt();
                int v = sc.nextInt();
                a[u].add(v);
                a[v].add(u);
            }
            int[] color = new int[n+1];
            boolean ok = true;
            for (int i=1; i<=n; i++) {
                if (color[i] == 0) {
                    if (dfs(a, color, i, 1) == false) {
                        ok = false;
                    }
                }
            }
            if (ok) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }

    }
}