图专项——二分图

二分图：节点由两个集合组成，且两个集合内部没有边的图。

通俗一点就是：如果两个集合中的点分别染成黑色和白色，可以发现二分图中的每一条边都一定是连接一个黑色点和一个白色点。

可以通过DFS 或者 BFS 遍历该图

题目连接https://www.luogu.org/problemnew/show/P1330

题解：每一条边都有且仅有一个被它所连接的点被选中。可以通过二分图解决。 由于此题中可能存在多个连通分支，所以要对所有的点进行bfs，否则的话仅仅对一个点进行bfs即可。总的复杂度为$O(n+m)$

AC代码：

import java.util.ArrayList; import java.util.Scanner; /** * @author Hongchuan CAO * @version 1.0 * * Change the problem to dye color to the graph * There will have more than one connected graph so that we should apply dfs to all the node */ public class Main { private boolean[] use; private int[] color; private int[] num = new int [3]; private ArrayList<ArrayList<Integer>> graph; public Main(int n){ use = new boolean[n+1]; color = new int[n+1]; graph = new ArrayList<ArrayList<Integer>>(n+1); for(int i=0;i<=n;i++) graph.add(new ArrayList<Integer>()); } public void get_read(int m, Scanner in){ for(int i=1;i<=m;i++){ int inx = in.nextInt(); int iny = in.nextInt(); //undirected graph graph.get(inx).add(iny); graph.get(iny).add(inx); } } private boolean dfs(int index,int col){ use[index] = true; color[index] = col; num[col]++; //record the number of the color //dfs all the connected node for(int node : graph.get(index)){ //divide into three situation if(color[node] == col){ return false; }else{ if(!use[node]){ if(!dfs(node,3-col)){ return false; } } } } return true; } public void solve(int n){ int sum = 0; for(int i=1;i<=n;i++){ //get the number of the color 1 and 2 if(!use[i]){ num[1]=0; num[2]=0; if(dfs(i,1)){ sum += Math.min(num[1],num[2]); //calculate each connected graph }else{ System.out.println("Impossible"); return; } } } System.out.println(sum); } public static void main(String arg[]){ Scanner in = new Scanner(System.in); int n,m; n=in.nextInt(); m=in.nextInt(); Main pro = new Main(n); pro.get_read(m,in); pro.solve(n); } }