給定一個n個點m條邊的無向圖，圖中可能存在重邊和自環，
請你判斷這個圖是否是二分圖，
輸入格式
第一行包含兩個整數n和m，
接下來m行，每行包含兩個整數u和v，表示點u和點v之間存在一條邊，
輸出格式
如果給定圖是二分圖，則輸出“Yes”，否則輸出“No”，
資料范圍
1≤n,m≤1051≤n,m≤105
輸入樣例：
4 4
1 3
1 4
2 3
2 4
輸出樣例：
Yes
二分圖：當且僅當圖中不含奇數環
奇數環：環中邊的數目是奇數
圖中不含奇數環，則染色程序中一定沒有矛盾
代碼：
//染色法思路：從一個點開始染色，相鄰點染不同顏色 //原理：如果不存在奇數環，則染色程序中不會出現染色沖突 //時間復雜度：n+m n個點向外遍歷共m條邊 //二分圖：當且僅當圖中不含奇數環 //奇數環：環中邊的數目是奇數 //圖中不含奇數環，則染色程序中一定沒有矛盾 import java.util.Arrays; import java.util.Scanner; public class Main{ static final int N=100005,M=2*N; static int h[]=new int[N]; static int e[]=new int[M]; static int ne[]=new int[M]; static int n,m,idx; static int color[]=new int[N]; static void add(int a,int b){ e[idx]=b; ne[idx]=h[a]; h[a]=idx++; } //染色法 static boolean dfs(int u,int c){ color[u]=c; for(int i=h[u];i!=-1;i=ne[i]){//給點u的所有鄰接點染色 int j=e[i]; if(color[j]==0){//如果沒有沒染過色，就染色 if(!dfs(j,3-c)) return false; } else if(color[j]==c) return false;//如果染過色并且和當前點u顏色相同，就不是二分圖 } return true; } public static void main(String[] args) { Scanner scan=new Scanner(System.in); n=scan.nextInt(); m=scan.nextInt(); Arrays.fill(h, -1); while(m-->0){ int a=scan.nextInt(); int b=scan.nextInt(); add(a,b); add(b,a); } boolean flag=true; for(int i=1;i<=n;i++)//圖可能不連通，所以每個點都要遍歷 if(color[i]==0){//當前點沒染過色 if(!dfs(i,1)){ flag=false; break; } } if(flag) System.out.println("Yes"); else System.out.println("No"); } }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/95244.html
標籤：其他