二分圖判斷
二分圖：將所有點(diǎn)分成兩個(gè)集合盐欺，使得所有邊只出現(xiàn)在集合之間赁豆。一定不含有奇數(shù)環(huán)，可能含有長(zhǎng)度為偶數(shù)的環(huán)冗美，不一定是連通圖魔种。
染色法
存儲(chǔ)結(jié)構(gòu)：鄰接表
dfs 思路：
- 染色可以使用 1 和 2 區(qū)分不同顏色，用 0 表示未染色
- 遍歷所有點(diǎn)粉洼，每次將為染色的點(diǎn)進(jìn)行dfs节预，默認(rèn)染成1或2
- 某個(gè)點(diǎn)某個(gè)點(diǎn)染色成功不代表整個(gè)圖就是二分圖
- 當(dāng)某個(gè)點(diǎn)染色失敗時(shí)，這個(gè)圖不是二分圖
- 染色失敗相當(dāng)于相鄰的 2 個(gè)點(diǎn)染了相同的顏色属韧。
代碼實(shí)現(xiàn)
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;
}
最大匹配
匹配：在圖論中安拟，一個(gè)“匹配”是一個(gè)邊的集合，其中任意兩條邊都沒(méi)有公共頂點(diǎn)
最大匹配：一個(gè)圖所有匹配中挫剑，所含匹配邊數(shù)最多的匹配去扣，稱(chēng)為這個(gè)圖的最大匹配。
完美匹配：在一個(gè)圖的某個(gè)匹配中，所有頂點(diǎn)都是匹配點(diǎn)愉棱。
交替路：從一個(gè)未匹配的點(diǎn)出發(fā)唆铐，依次經(jīng)過(guò)非匹配邊，匹配邊奔滑，非匹配邊...形成的路徑艾岂。
增廣路：從一個(gè)匹配點(diǎn)出發(fā)，走交替路朋其，如果途徑另一個(gè)未匹配點(diǎn)王浴，則這條交替路為增廣路。
匈牙利算法
存儲(chǔ)結(jié)構(gòu)：鄰接表
算法思路： a 找到 點(diǎn) b進(jìn)行匹配如果 b沒(méi)有進(jìn)行匹配梅猿，則 a , b進(jìn)行匹配 , 記為 match[b] = a氓辣。如果 b點(diǎn)已經(jīng)進(jìn)行匹配了 ，則看 匹配 b點(diǎn)的點(diǎn) match[b]能否找到另一個(gè)匹配點(diǎn)袱蚓，把改點(diǎn)匹配讓給 a 钞啸，如果可以，則匹配成功喇潘，如果不可以則匹配失敗体斩。
通俗例子：
如果你想找的妹子已經(jīng)有了男朋友，
你就去問(wèn)問(wèn)她男朋友颖低，
你有沒(méi)有備胎絮吵，
把這個(gè)讓給我好吧
實(shí)現(xiàn)代碼：
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 ++ ){
// 標(biāo)記右邊的圖的節(jié)點(diǎn)是否被訪問(wèn)過(guò)，每一次匹配被訪問(wèn)的情況都不一樣
// 所以每一次匹配都需要初始化
Arrays.fill(st , false );
if( find(i) ) ans++;
}
System.out.println(ans);
}
}
最小點(diǎn)覆蓋 ：選擇最少的點(diǎn)覆蓋所有的邊
最小點(diǎn)覆蓋 == 最大匹配數(shù)
最大獨(dú)立集：選出最多的點(diǎn)忱屑，使得所選出的點(diǎn)之間沒(méi)有邊蹬敲。
< == > 去掉最少的點(diǎn)，將所有邊都破壞掉
< == > 找最小覆蓋點(diǎn)
< == > 最大匹配
最大獨(dú)立集 = 總點(diǎn)數(shù) - 最大匹配
最小路徑點(diǎn)覆蓋（最小路徑覆蓋）：有向無(wú)環(huán)圖中想幻，用最少的粱栖，互不相交的路徑（點(diǎn)不重復(fù)），將所有點(diǎn)覆蓋脏毯。
思路：拆點(diǎn) a -> b 變成 a -> b' 闹究，然后原來(lái)的 結(jié)點(diǎn) v 和 新的結(jié)點(diǎn) v'就構(gòu)成了二分圖。例如 路徑 1 -> 2 -> 3 變成 1 -> 2' 食店， 2 - > 3'渣淤。
新二分圖中
<==> 讓左側(cè)的非匹配點(diǎn)最少
<==> 讓左側(cè)匹配點(diǎn)最多
<==> 找最大匹配
最小路徑點(diǎn)覆蓋 = 結(jié)點(diǎn)數(shù) - 最大匹配
最小路徑可重復(fù)覆蓋：選取最少可相交的邊覆蓋全部頂點(diǎn)。
思路：
1）求原圖的傳遞閉包
2）在新圖中求最小路徑覆蓋
#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];
//在具體求二分圖最大匹配的時(shí)候并沒(méi)有真的構(gòu)造出圖 G —— 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;
}
歐拉路徑
歐拉路徑：一條能夠不重不漏地經(jīng)過(guò)圖上的每一條邊的路徑吉嫩。
歐拉回路：起點(diǎn)和終點(diǎn)相同的歐拉路徑价认。
-
1，對(duì)于無(wú)向圖自娩，所有邊都是連通的：
- 1）存在歐拉路徑的充分必要條件：度數(shù)為奇數(shù)的點(diǎn)只能有0個(gè)或2個(gè)用踩。
- 2） 存在歐拉回路的充分必要條件：度數(shù)為奇數(shù)的點(diǎn)只能有0個(gè)。
-
2 ，對(duì)于有向圖脐彩，所有邊都是連通的：
- 1）存在歐拉路徑的充分必要條件：要么所有點(diǎn)的出度均等于入度碎乃；要么除了兩個(gè)點(diǎn)以外，所有的點(diǎn)的出度均等于入度惠奸，剩余的兩個(gè)點(diǎn)梅誓，一個(gè)出度比入度多 1 （起點(diǎn)），另一個(gè)入度比出度多 1 （終點(diǎn)）佛南。
- 2） 存在歐拉回路的充分必要條件：所有點(diǎn)的出度均等于入度梗掰。
#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;
}
