6-3: 이분그래프 판별

이분그래프 판별

 

문제

---

이분 그래프란, 아래 그림과 같이 정점을 크게 두 집합으로 나눌 수 있는 그래프를 말한다. 여기서 같은 집합에 속한 정점끼리는 간선이 존재해서는 안된다. 예를 들어, 아래 그래프의 경우 정점을 크게 {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

import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;

public class GraphIntoTwoSets {
    /**
     *
     *
     * 이분 그래프란, 아래 그림과 같이 정점을 크게 두 집합으로 나눌 수 있는 그래프를 말한다.
     * 여기서 같은 집합에 속한 정점끼리는 간선이 존재해서는 안된다.
     * 예를 들어, 아래 그래프의 경우 정점을 크게 {1, 4, 5}, {2, 3, 6} 의 두 개의 집합으로 나누게 되면, 같은 집합에 속한 정점 사이에는 간선이 존재하지 않으므로 이분 그래프라고 할 수 있다.
     *
     *
     *
     * @param args
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int numNodes = sc.nextInt();
        int numEdges = sc.nextInt();

        Graph graph = new Graph(numNodes);

        //add nodes
        for (int i=0; i<numNodes; i++){
            Node node = new Node(i);
            graph.nodeArr[i] = node;
        }

        //add edges
        for (int i=0; i<numEdges;i++){
            int start = sc.nextInt()-1;
            int end = sc.nextInt()-1;
            graph.adjacencyMatrix[start][end] = true;
            graph.adjacencyMatrix[end][start] = true;
        }

        graph.nodeArr[0].side = "left";

        dfs(graph, graph.nodeArr[0]);

    }

    private static void dfs(Graph graph, Node start) {
        if (start == null){
            return;
        }

        ArrayDeque<Node> stack = new ArrayDeque<>();
        stack.push(start);

        while(!stack.isEmpty()){
            Node temp = stack.pop();
            if (!temp.visited){
//                System.out.println(temp.data + " " + temp.color);

                temp.visited = true;
//                System.out.print(temp.data + " ");
                //look at its edges, and push onto stack.
                for (int i=0; i<graph.adjacencyMatrix[temp.data].length; i++){
                    if (graph.adjacencyMatrix[temp.data][graph.adjacencyMatrix[temp.data].length-i-1]){
                        //is edge.
                        if (graph.nodeArr[temp.data].side.equals("left")){
                            graph.nodeArr[graph.adjacencyMatrix[temp.data].length-i-1].side = "right";
                        } else {
                            graph.nodeArr[graph.adjacencyMatrix[temp.data].length-i-1].side = "left";
                        }
                        stack.push(graph.nodeArr[graph.adjacencyMatrix[temp.data].length-i-1]);
                    }
                }
            } else {
                //if already visited, check if color is equal
                //look at its edges, and push onto stack.
                for (int i=0; i<graph.adjacencyMatrix[temp.data].length; i++){
                    if (graph.adjacencyMatrix[temp.data][graph.adjacencyMatrix[temp.data].length-i-1]){
                        //is edge.
                        if (graph.nodeArr[temp.data].side.equals(graph.nodeArr[graph.adjacencyMatrix[temp.data].length-i-1].side)){
                            System.out.print("No");
                            return;
                        }
                    }
                }
            }
        }

        System.out.print("Yes");

    }

    public static class Graph{

        Node[] nodeArr;
        boolean[][] adjacencyMatrix;

        public Graph(int N){
            nodeArr = new Node[N];
            adjacencyMatrix = new boolean[N][N];
        }
    }

    public static class Node{
        int data;
        boolean visited;
        String side;


        public Node(int data){
            this.data = data;
        }
    }
}