二分图判断
二分图：将所有点分成两个集合，使得所有边只出现在集合之间。一定不含有奇数环，可能含有长度为偶数的环，不一定是连通图。
染色法
存储结构：邻接表
dfs 思路：
- 染色可以使用 1 和 2 区分不同颜色，用 0 表示未染色
- 遍历所有点，每次将为染色的点进行dfs，默认染成1或2
- 某个点某个点染色成功不代表整个图就是二分图
- 当某个点染色失败时，这个图不是二分图
- 染色失败相当于相邻的 2 个点染了相同的颜色。
代码实现
boolean ans = true;
for(int i = 1 ; i <= n ;i ++){
if( st[i] == 0 && !dfs( i , 1 ) ){
ans = false;
break;
}
}
static boolean dfs(int u , int color){
st[u] = color;
for(int i = h[u] ; i != -1 ; i = ne[i] ){
int j = e[i];
if( st[j] == 0 && !dfs(j ,3 - color)) return false;
if( st[j] == color ) return false;
}
return true;
}
bfs代码：
static boolean bfs(){
Queue<Integer> queue = new LinkedList<>();
int[] st = new int[N];
for(int i = 1 ; i <= n ;i ++ ){
if( st[i] == 0 ){
st[i] = 1;
queue.add(i);
while( !queue.isEmpty() ){
int u = queue.poll();
for(int k = h[u] ; k != -1 ; k = ne[k] ){
int j = e[k];
if( st[j] == st[u] ) return false;
if( st[j] == 0 ){
st[j] = 3 - st[u];
queue.add(j);
}
}
}
}
}
return true;
}
最大匹配
匹配：在图论中，一个“匹配”是一个边的集合，其中任意两条边都没有公共顶点
最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。
完美匹配：在一个图的某个匹配中，所有顶点都是匹配点。
交替路：从一个未匹配的点出发，依次经过非匹配边，匹配边，非匹配边...形成的路径。
增广路：从一个匹配点出发，走交替路，如果途径另一个未匹配点，则这条交替路为增广路。
匈牙利算法
存储结构：邻接表
算法思路： a 找到 点 b进行匹配如果 b没有进行匹配，则 a , b进行匹配 , 记为 match[b] = a。如果 b点已经进行匹配了 ，则看 匹配 b点的点 match[b]能否找到另一个匹配点，把改点匹配让给 a ，如果可以，则匹配成功，如果不可以则匹配失败。
通俗例子：
如果你想找的妹子已经有了男朋友，
你就去问问她男朋友，
你有没有备胎，
把这个让给我好吧
image.png
实现代码：
import java.util.*;
public class Main{
static int N = 510;
static int M = 100010;
static int[] h , e , ne;
static int idx;
static int[] match;
static boolean[] st;
static{
h = new int[N];
match = new int[N];
st = new boolean[N];
e = new int[M];
ne = new int[M];
Arrays.fill( h , -1 );
}
static void add(int a ,int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
static boolean find(int x ){
for(int i = h[x] ; i != -1 ; i = ne[i] ){
int j = e[i];
if( !st[j] ){
st[j] = true;
if( match[j] == 0 || find( match[j] ) ){
match[j] = x;
st[j] = true;
return true;
}
}
}
return false;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n1 = sc.nextInt() , n2 = sc.nextInt() , m = sc.nextInt();
while(m -- > 0){
int a = sc.nextInt() , b = sc.nextInt();
add(a , b);
}
int ans = 0 ;
for(int i = 1 ; i <= n1 ; i ++ ){
// 标记右边的图的节点是否被访问过，每一次匹配被访问的情况都不一样
// 所以每一次匹配都需要初始化
Arrays.fill(st , false );
if( find(i) ) ans++;
}
System.out.println(ans);
}
}
最小点覆盖 ：选择最少的点覆盖所有的边
最小点覆盖 == 最大匹配数
最大独立集：选出最多的点，使得所选出的点之间没有边。
< == > 去掉最少的点，将所有边都破坏掉
< == > 找最小覆盖点
< == > 最大匹配
最大独立集 = 总点数 - 最大匹配
最小路径点覆盖（最小路径覆盖）：有向无环图中，用最少的，互不相交的路径（点不重复），将所有点覆盖。
思路：拆点 a -> b 变成 a -> b' ，然后原来的 结点 v 和 新的结点 v'就构成了二分图。例如 路径 1 -> 2 -> 3 变成 1 -> 2' ， 2 - > 3'。
新二分图中
<==> 让左侧的非匹配点最少
<==> 让左侧匹配点最多
<==> 找最大匹配
最小路径点覆盖 = 结点数 - 最大匹配
最小路径可重复覆盖：选取最少可相交的边覆盖全部顶点。
思路：
1）求原图的传递闭包
2）在新图中求最小路径覆盖
image.png
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 210;
int n , m;
int match[N];
bool g[N][N] , st[N];
bool find(int x)
{
for(int i = 1 ; i <= n ;i ++ )
if( g[x][i] && !st[i] )
{
st[i] = true;
if( !match[i] || find(match[i]) )
{
match[i] = x;
return true;
}
}
return false;
}
int main()
{
cin >> n >> m;
while(m--)
{
int x , y;
cin >> x >> y;
g[x][y] = true;
}
//求传递闭包
for(int k = 1 ; k <= n ;k ++ )
for(int i = 1 ; i <= n ;i ++ )
for(int j = 1 ; j <= n ;j ++ )
g[i][j] |= g[i][k] & g[k][j];
//在具体求二分图最大匹配的时候并没有真的构造出图 G —— G'
//而是把它想象成一个这样子的二分图
int cnt = 0;
for(int i = 1 ; i <= n ;i ++)
{
memset(st ,0 ,sizeof st);
if( find(i) ) cnt ++;
}
cout << n - cnt << endl;
return 0;
}
欧拉路径
欧拉路径：一条能够不重不漏地经过图上的每一条边的路径。
欧拉回路：起点和终点相同的欧拉路径。
-
1，对于无向图，所有边都是连通的：
- 1）存在欧拉路径的充分必要条件：度数为奇数的点只能有0个或2个。
- 2） 存在欧拉回路的充分必要条件：度数为奇数的点只能有0个。
-
2 ，对于有向图，所有边都是连通的：
- 1）存在欧拉路径的充分必要条件：要么所有点的出度均等于入度；要么除了两个点以外，所有的点的出度均等于入度，剩余的两个点，一个出度比入度多 1 （起点），另一个入度比出度多 1 （终点）。
- 2） 存在欧拉回路的充分必要条件：所有点的出度均等于入度。
image.png
#include<cstring>
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 100010 , M = 400010;
int type;
int n , m;
int h[N] , e[M] , ne[M] , idx;
int ans[M / 2] , din[N] , dout[N] , cnt;
bool used[M];
void add(int a ,int b)
{
e[idx] = b , ne[idx] = h[a] , h[a] = idx ++;
}
void dfs(int u )
{
for(int &i = h[u] ; ~i ; )
{
if( used[i] )
{
i = ne[i] ;
continue;
}
used[i] = true;
if( type == 1 ) used[i ^ 1] = true;
int t;
if( type == 1 )
{
t = i / 2 + 1;
if( i & 1 ) t = -t;
}
else t = i + 1;
int j = e[i];
i = ne[i];
dfs(j);
ans[++ cnt] = t;
}
}
int main()
{
scanf("%d",&type);
scanf("%d%d" , &n ,&m);
memset(h , -1 ,sizeof h);
for(int i = 0 ; i < m ;i ++ )
{
int a , b;
scanf("%d%d" ,&a ,&b);
add(a , b);
if( type == 1 ) add(b , a) ;
din[b] ++ , dout[a] ++ ;
}
if( type == 1 )
{
for(int i = 1 ; i <= n ;i ++ )
if( din[i] + dout[i] & 1 )
{
puts("NO");
return 0;
}
}
else
{
for(int i = 1 ; i <= n ;i ++ )
if( din[i] != dout[i] )
{
puts("NO");
return 0;
}
}
for(int i = 1; i <= n ;i ++ )
if( h[i] != -1 )
{
dfs(i);
break;
}
if( cnt < m )
{
puts("NO");
return 0;
}
puts("YES");
for(int i = cnt ; i ; i -- ) printf("%d ",ans[i]);
puts("");
return 0;
}
