# Bipartial Graph - Part I - 二分圖一?二分圖判定 ### Source - [hihoCoder](http://hihocoder.com/problemset/problem/1121) ### Problem 時間限制:10000ms 單點時限:1000ms 內存限制:256MB #### 描述 大家好，我是小Hi和小Ho的小伙伴Nettle，從這個星期開始由我來完成我們的Weekly。 新年回家，又到了一年一度大齡剩男剩女的相親時間。Nettle去姑姑家玩的時候看到了一張姑姑寫的相親情況表，上面都是姑姑介紹相親的剩男剩女們。每行有2個名字，表示這兩個人有一場相親。由于姑姑年齡比較大了記性不是太好，加上相親的人很多，所以姑姑一時也想不起來其中有些人的性別。因此她拜托我檢查一下相親表里面有沒有錯誤的記錄，即是否把兩個同性安排了相親。 OK，讓我們愉快的**暴力搜索**吧！ 才怪咧。 對于拿到的相親情況表，我們不妨將其轉化成一個圖。將每一個人作為一個點**(編號1..N)**，若兩個人之間有一場相親，則在對應的點之間連接一條無向邊。(如下圖)  因為相親總是在男女之間進行的，所以每一條邊的兩邊對應的人總是不同性別。假設表示男性的節點染成白色，女性的節點染色黑色。對于得到的無向圖來說，即每一條邊的兩端一定是一白一黑。如果存在一條邊兩端同為白色或者黑色，則表示這一條邊所表示的記錄有誤。 由于我們并不知道每個人的性別，我們的問題就轉化為**判定是否存在一個合理的染色方案，使得我們所建立的無向圖滿足每一條邊兩端的頂點顏色都不相同**。 那么，我們不妨將所有的點初始為未染色的狀態。隨機選擇一個點，將其染成白色。再以它為起點，將所有相鄰的點染成黑色。再以這些黑色的點為起點，將所有與其相鄰未染色的點染成白色。不斷重復直到整個圖都染色完成。(如下圖)  在染色的過程中，我們應該怎樣發現錯誤的記錄呢？相信你一定發現了吧。對于一個已經染色的點，如果存在一個與它相鄰的已染色點和它的顏色相同，那么就一定存在一條錯誤的記錄。(如上圖的4，5節點) 到此我們就得到了整個圖的算法： 1. 選取一個未染色的點u進行染色 1. 遍歷u的相鄰節點v：若v未染色，則染色成與u不同的顏色，并對v重復第2步；若v已經染色，如果 u和v顏色相同，判定不可行退出遍歷。 1. 若所有節點均已染色，則判定可行。 接下來就動手寫寫吧！ #### 輸入 第1行：1個正整數T(1≤T≤10) 接下來T組數據，每組數據按照以下格式給出： 第1行：2個正整數N,M(1≤N≤10,000，1≤M≤40,000) 第2..M+1行：每行兩個整數u,v表示u和v之間有一條邊 #### 輸出 第1..T行：第i行表示第i組數據是否有誤。如果是正確的數據輸出”Correct”，否則輸出”Wrong” 樣例輸入 ~~~ 2 5 5 1 2 1 3 3 4 5 2 1 5 5 5 1 2 1 3 3 4 5 2 3 5 ~~~ 樣例輸出 ~~~ Wrong Correct ~~~ ### 題解 二分圖中最簡單的題，思路原文中已提到，這里就不贅述了，簡單實現的話可以使用二維數組，如果要模擬圖的操作的話可以自定義類。 ### Java ~~~ import java.util.*; import java.util.Queue; class UndirectedGraphNode { int label; int color; ArrayList<UndirectedGraphNode> neighbors; UndirectedGraphNode(int x) { this.label = x; this.color = 0; this.neighbors = new ArrayList<UndirectedGraphNode>(); } } public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int T = in.nextInt(); for (int i = 1; i <= T; i++) { int N = in.nextInt(); int M = in.nextInt(); // initialize graph List<UndirectedGraphNode> graph = new ArrayList<UndirectedGraphNode>(); for (int n = 1; n <= N; n++) { graph.add(new UndirectedGraphNode(n)); } // construct graph for (int j = 1; j <= M; j++) { int u = in.nextInt(), v = in.nextInt(); graph.get(u - 1).neighbors.add(graph.get(v - 1)); graph.get(v - 1).neighbors.add(graph.get(u - 1)); } // solve if (solve(graph)) { System.out.println("Correct"); } else { System.out.println("Wrong"); } } } public static boolean solve(List<UndirectedGraphNode> graph) { // 1 for white, -1 for black, 0 for uncolored for (UndirectedGraphNode node : graph) { if (node.color == 0) { node.color = 1; Queue<UndirectedGraphNode> q = new LinkedList<UndirectedGraphNode>(); q.offer(node); while (!q.isEmpty()) { int qSize = q.size(); for (int i = 0; i < qSize; i++) { UndirectedGraphNode qNode = q.poll(); for (UndirectedGraphNode neighbor : qNode.neighbors) { if (neighbor.color == 0) { neighbor.color = -1 * qNode.color; q.offer(neighbor); } else if (neighbor.color + qNode.color != 0) { // the color of qNode is the same with neighbor return false; } } } } } } return true; } } ~~~ ### 源碼分析 使用 [BFS](# "Breadth-First Search, 廣度優先搜索") 不容易爆棧。 ### 復雜度分析 時間復雜度 O(V+E)O(V + E)O(V+E).