이분그래프

이분그래프 판별

 

문제

---

이분 그래프란, 아래 그림과 같이 정점을 크게 두 집합으로 나눌 수 있는 그래프를 말한다. 여기서 같은 집합에 속한 정점끼리는 간선이 존재해서는 안된다. 예를 들어, 아래 그래프의 경우 정점을 크게 {1, 4, 5}, {2, 3, 6} 의 두 개의 집합으로 나누게 되면, 같은 집합에 속한 정점 사이에는 간선이 존재하지 않으므로 이분 그래프라고 할 수 있다.

그래프가 입력으로 주어질 때, 이 그래프가 이분그래프인지를 판별하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. ( 1 ≤ N ≤ 1,000, 1 ≤ M ≤ 100,000 ) 둘째 줄부터 간선의 정보가 주어진다. 각 줄은 두 개의 숫자 a, b로 이루어져 있으며, 이는 정점 a와 정점 b가 연결되어 있다는 의미이다.  

출력

---

주어진 그래프가 이분 그래프이면 Yes, 아니면 No를 출력한다.

 

예제 입력

6 5
1 2
2 4
3 4
3 5
4 6

예제 출력

Yes

 

예제 입력

4 5
1 2
1 3
1 4
2 4
3 4

예제 출력

No

코드

//2색 칠하기

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    public static ArrayList<Node> box = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //총 몇개의 숫자를 입력 받을 것인지
        int a;
        int b;
        int c = 0;
        int d = 0;
        Queue<Node> q = new LinkedList<>();

        a = sc.nextInt();

        for (int i = 0; i <= a; i++) {
            Node node = new Node(i);
            box.add(node);
        }

        b = sc.nextInt();

        for (int i = 0; i < b; i++) {
            c = sc.nextInt();
            d = sc.nextInt();
            box.get(c).getNodes().add(box.get(d));
        }

        q.offer(box.get(1));
        if (canColor(q)) System.out.println("Yes");
        else System.out.println("No");
    }

    public static boolean canColor(Queue<Node> q) {
        Node node;
        ArrayList<Node> datas;

        while (!q.isEmpty()) {
            node = q.poll();
            datas = node.getNodes();

            for (Node data :
                    datas) {
                if (!data.isChecked()) {
                    q.offer(data);
                    data.setColor(!node.isColor());
                    data.setChecked(true);
                } else {
                    if (node.isColor() == data.isColor()) return false;
                }

            }
        }

        return true;
    }


}


class Node {


    private boolean color;
    private boolean isChecked;
    private int data;
    private ArrayList<Node> nodes;

    public boolean isColor() {
        return color;
    }

    public void setColor(boolean color) {
        this.color = color;
    }


    public boolean isChecked() {
        return isChecked;
    }

    public void setChecked(boolean checked) {
        isChecked = checked;
    }

    public Node(int data) {
        this.setChecked(false);
        this.data = data;
        nodes = new ArrayList<>();
    }

    public ArrayList<Node> getNodes() {
        return nodes;
    }

}