二分图定义：将所有点分成两个集合，使得所有边只出现在集合之间，就是二分图
目录
860. 染色法判定二分图
1、dfs
2、bfs
861. 二分图的最大匹配 - 匈牙利算法ntr算法
860. 染色法判定二分图
活动 - AcWing
1、dfs
思路：
- 对每一个未染色的点进行dfs，如果有一个点染色失败，说明该图不是二分图
- 在dfs中，先对该点染色，接着遍历所有相邻节点
- 如果相邻的点颜色和该点相同，说明该图不是二分图
- 如果相邻点未染色，则将该点染成相反色，并递归其相邻点
- 如果所有点均为出现染色失败的情况，则该图为二分图
import java.util.*;
class Main
{
static int N=100010,M=N*2;
static int[] h=new int[N],e=new int[M],ne=new int[M],color=new int[N];
static int idx;
public static void add(int a,int b)
{
e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
public static boolean dfs(int u,int c)
{
color[u]=c; //先给该点染色
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(color[j]==c) return false; //如果相邻点染色与该点一样
if(color[j]==0&&!dfs(j,3-c)) return false; //如果未染色且染色失败
}
return true;
}
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
Arrays.fill(h,-1);
int n=sc.nextInt(),m=sc.nextInt();
for(int i=0;i<m;i++)
{
int a=sc.nextInt(),b=sc.nextInt();
add(a,b); add(b,a);
}
for(int i=1;i<=n;i++)
if(color[i]==0)
if(!dfs(i,1))
{
System.out.print("No");
return;
}
System.out.print("Yes");
}
}2、bfs
思路：
- 对每一个未染色的点进行bfs
- 在bfs中，先给该点染色，将其放入队列
- 队列循环放出与其相邻节点，如果有节点色和该点相同，则不是二分图
- 否则将未染色的点，染与该点相反的色，存入队列中
- 如果队空，没有出现染色失败的情况，则该图是二分图
import java.util.*;
class Main
{
static int N=100010,M=N*2;
static int[] h=new int[N],e=new int[M],ne=new int[M],color=new int[N];
static int idx;
public static void add(int a,int b)
{
e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
public static boolean bfs(int u)
{
color[u]=1; //先给该点染色
Queue<PII> q=new LinkedList<>();
q.offer(new PII(u,1));
while(!q.isEmpty())
{
PII t=q.poll();
int p=t.x,c=t.y;
for(int i=h[p];i!=-1;i=ne[i])
{
int j=e[i];
if(color[j]==c) return false;
if(color[j]==0)
{
q.offer(new PII(j,3-c));
color[j]=3-c;
}
}
}
return true;
}
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
Arrays.fill(h,-1);
int n=sc.nextInt(),m=sc.nextInt();
for(int i=0;i<m;i++)
{
int a=sc.nextInt(),b=sc.nextInt();
add(a,b); add(b,a);
}
for(int i=1;i<=n;i++)
if(color[i]==0)
if(!bfs(i))
{
System.out.print("No");
return;
}
System.out.print("Yes");
}
}
class PII
{
int x,y;
PII(int x,int y)
{
this.x=x;
this.y=y;
}
}
861. 二分图的最大匹配 - 匈牙利算法ntr算法
活动 - AcWing
思路：
匹配：在图论中，一个「匹配」是一个边的集合，其中任意两条边都没有公共顶点
最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配
import java.util.*;
class Main
{
static int N=510,M=100010;
static int[] h=new int[N],e=new int[M],ne=new int[M];
static int[] st=new int[N]; //用于标记已经考虑过的妹子
static int[] match=new int[N]; //用于记录当前妹子的对象
static int idx;
public static void add(int a,int b)
{
e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
public static boolean find(int u)
{
//枚举这个男生看上的所有妹子
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(st[j]==0) //如果这个妹子未匹配成功
{
st[j]=1;
if(match[j]==0||find(match[j])) //如果这妹子没对象or妹子有对象，但她对象有备胎
{
match[j]=u; //两对皆大欢喜，妹子换了新对象，前任跟备胎在一起了，两对匹配成功
return true;
}
}
}
return false;
}
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
Arrays.fill(h,-1);
int n1=sc.nextInt(),n2=sc.nextInt(),m=sc.nextInt();
for(int i=0;i<m;i++)
{
int a=sc.nextInt(),b=sc.nextInt();
add(a,b); //只需要男生找女生
}
int res=0;
for(int i=1;i<=n1;i++) //遍历每个男生
{
Arrays.fill(st,0); //从头开始考虑妹子
if(find(i)) res++; //如果这个男生能找到妹子，则匹配数+1
}
System.out.print(res);
}
}
