860. 染色法判定二分图(模板)

给定一个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");
        }
}

 

上一篇:线性同余方程(同余+扩展欧几里得模板)


下一篇:算法练习(1)