「Algorithm」03 搜索与图论

深度优先搜索DFS
广度优先搜索BFS
树与图的存储、深搜、广搜
拓扑排序
最短路
最小生成树
二分图

DFS和BFS

BFS是queue，O（2^n）是可以找最短路

DFS是stack，O（n）不具有最短程

DFS：

求全排列的过程。

#include<iostream>
using namespace std;

const int N = 10;

int n;
int path[N];
bool st[N];

void dfs(int u)
{
    if(u == n)
    {
        for(int i = 0; i < n; ++ i)
            cout << path[i] << " ";
        puts("");
        return;
    }
    for(int i = 1; i <= n; ++i)
        if(!st[i]){
            path[u] = i;
            st[i] = true;
            dfs(u + 1);
            st[i] = false;
        }

}

int main(){
    cin >> n;
    
    dfs(0);
    
    return 0;
}

n皇后问题：

考虑对角线

#include<iostream>

using namespace std;

const int N = 20;

int n;
char g[N][N];
int col[N], dg[N], udg[N];
//col是列，dg是对角线，udg是右对角线

void dfs(int u)
{
    if (u == n)
    {
        for(int i = 0; i < n; ++ i) puts(g[i]);      
        puts("");
        return;
    }
    
    for(int i = 0; i < n; ++ i)
    {
        if(!col[i] && !dg[u + i] && !udg[i - u + n]){
        //i是y, u是x
            g[u][i] = 'Q';
            col[i] = dg[u+i] = udg[i - u + n] = true;
            dfs(u + 1);
            col[i] = dg[u+i] = udg[i - u + n] = false;
            g[u][i] = '.';
        }      
    }
}

int main(){
    
    cin >> n;
    
    for(int i = 0; i < n ; ++ i)
        for(int j = 0;  j< n; ++ j)
            g[i][j] = '.';
    dfs(0);
    return 0;
}

BFS

求最短路，必须权重为1

走迷宫：

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 110;

int n, m;
int g[N][N];
int d[N][N]; //d数组存放此点到起点的距离。
PII q[N * N]; //表示搜索过程中的坐标点
PII pre[N][N];//记录每个点之前的点

int bfs()
{
    int hh = 0, tt = -1;
    q[++ tt] = {0, 0};
    
    memset(d, -1, sizeof d);
    d[0][0] = 0;
    
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    
    
    while(hh <= tt)
    {
        auto t = q[hh ++];
        
        for(int i = 0; i < 4; ++ i)
        {
            int x = t.first + dx[i], y = t.second + dy[i];
            //g[x][y] == 0说明可以走，d[x][y] == -1，说明没有赋值，说明没有走过
            if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1)
            {
                d[x][y] = d[t.first][t.second]  + 1;
                pre[x][y] = t;
                q[++ tt] = {x,y};
            }
        }
    }
    
    int x = n - 1, y = m - 1;
    while(x || y){
        cout << x << ' ' << y << endl;
        auto t = pre[x][y];
        x = t.first, y = t.second;
    }
		//输出路径，反着
    
    return d[n-1][m-1];
}

int main(){
    cin >> n >> m;
    
    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < m; ++ j)
            cin >> g[i][j];
    
    cout << bfs() << endl;
        
    
    return 0;
}

树和图

有向图和无向图

a→b

有向图的存储：

邻接矩阵 G[a, b]表示a→b
邻接表 n各点，每个单链表

图的深搜

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = N * 2;

int n, m;
//h是n个链表头，e是节点的值，ne是节点的指针。
int h[N], e[M], ne[M], idx;
bool st[N]; //标记作用

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

void dfs(int u)
{
    st[u] = true;

    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!st[j]) dfs(j);
    }

}

int main()
{
    memset(h, -1, sizeof h);
    dfs(1);

    return 0;
}

树的重心：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = N * 2;

int n;
//h是n个链表头，e是节点的值，ne是节点的指针。
int h[N], e[M], ne[M], idx;
bool st[N]; //标记作用

int ans = N;

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx;
    idx++;
}

//返回以u为根的树的节点的数量
int dfs(int u)
{
    st[u] = true;
    
    int sum = 1, res = 0;
    //sum是以u为根的节点的数量
    //res记录删除该点u的联通块的点的数量的最大值
    //result的缩写是res
    
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!st[j]){
            int s = dfs(j);
            res = max(res, s);
            sum += s;
        } 
    }
    
    res = max(res, n - sum);
    ans = min(ans, res);
    return sum;
}

int main()
{
    memset(h, -1, sizeof h);
    
    cin >> n ;
    for(int i = 0; i < n -1; ++i)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }
    
    dfs(1);//从1开始，是因为输入的a,b是从1开始的。

    cout << ans << endl;
    return 0;
}

图的广搜

#include<iostream>
#include<cstring>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int h[N], e[N], ne[N], idx;

int d[N], q[N];//d是距离，q是队列

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx;
    idx ++;
}

int bfs()
{  
   int hh = 0, tt = -1;  
   
    q[++ tt] = 1;
    d[1] = 0;
    
    while(hh <= tt)
    {
        int t = q[hh ++];
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(d[j] == -1)
            {
                d[j] = d[t] + 1;
                q[++ tt] = j;
            }
        }
    }
    
    return d[n];
}

int main()
{
    cin >> n >> m;
    
    memset(h, -1, sizeof h);
    memset(d, -1, sizeof d);
    
    for(int i = 0; i < m; ++ i)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    
    cout << bfs() << endl;
    
    return 0;
}

848. 有向图的拓扑序列

起点在终点的前面，那么就是一个拓扑序列

有向无环图成为拓扑图。

入度：有几条边指向自己。
出度：自己有几条边出去。

入度为零，说明没有一个点在我前面。所以所有入度为零的点都可以排在最前面。

有向无环图一定存在一个入度为0的点。

假设所有点的入度都不是零，那么任选一个点，往上找n个点，然后就是找第n+1个点时，一定需要在n个点里取一个点，一定存在环。

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 100010;

int n, m;
int h[N], e[N], ne[N], idx;
int q[N], d[N];
//d是入度

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

bool topsort(){
    int hh = 0, tt = -1;
    
    for(int i = 1; i <= n; ++ i)
        if(!d[i])
            q[++ tt] = i;
    //把入度为0的入队
    
    while(hh <= tt)
    {
        int t = q[hh++];
        
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            d[j] --;
            if(d[j] == 0) q[ ++ tt] = j;
            //当入队的时候，保证是符合拓扑序列定义的
            //因为入队的元素，保证没有指向之前入队元素的边
            //因为入队元素的入度，是从再之前的入队元素删去的。
        }
    }
    //如果tt==n-1说明已经全部入队了，是有向的无环图
    return tt == n - 1;
}

int main()
{
    cin >> n >> m;    
    
    memset(h, -1, sizeof h);
    
    for(int i = 0; i < m; ++ i)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
        d[b] ++;
    }
    
    if(topsort())
    {
        for(int i = 0; i < n; ++ i)
            printf("%d ",q[i]);
        
    } else {
        puts("-1");
    }
    return 0;
}

最短路

最短路：

单源最短路：从1号点到n号的最短路
- 所有边权都是正数
  - 朴素的Dijkstra算法 O(n ^ 2)，
    - 适用于稠密图
  - 堆优化的Dijstra算法 O(mlogn)
    - 适用于稀疏图
    - m是边数
- 存在负权边
  - Bellman-Ford 算法 O(mn)
    - 不超过k条边的条件，必须用这个
  - SPFA算法，BF算法的优化 O(m)
多源汇最短路：求出任意2个顶点之间的最短路径，支持负权边
- Floyd算法，O(n^3)

朴素Dijkstra算法

适用稠密图。

单源最短路，从1号点到其他点的最短距离。

过程：

s是已经确定最短距离的点。

dis[1] = 0, dis[i] = +无穷
对于i from 2 to n, 找到不在s中的距离最近的点t。然后将t加入到s中，然后用t更新其他点的距离。

稠密图用领接矩阵。

稀释图用邻接表。

有向图和无向图的最短路一样。

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 510;

int n, m;
int g[N][N];
int dist[N];
bool st[N];
//dist 是距离
//st是标记

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    //初始g为最大值。
    dist[1] = 0;
    for(int i = 0; i < n; ++ i)
    {
        int t = -1;
        for(int j = 1; j <= n; ++ j)
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;       
				if(t == n)
						break;
				//提前break
        st[t] = true;
        
        for(int j = 1; j <= n; ++ j)
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
    
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main(){
    cin >> n >> m;
    
    //重边和自环可以处理，重边保留最短。
    memset(g, 0x3f, sizeof g);
    
    while(m --)
    {
        int a, b, c;
        cin >> a >> b >> c; 
        g[a][b] = min(g[a][b], c);
        
    }
    cout << dijkstra();

    return 0;
}

为什么Dijkstra不能处理负值？

依此标记A，C，B，D。但是标记完D之后，它只能更新B的dist的值，使得dist[B] = -201，但是C无法被更新。因为A、B无法再次访问了。所以负值有问题。

堆优化的Dijkstra算法

O(mlogn)，用堆的话，最后一步总共修改m次，每次是logn。

适用稀疏图，用邻接表

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 150000;

int n, m;
int h[N], e[N], ne[N], idx, w[N];
int dist[N];
bool st[N];

typedef pair<int, int> PII; 

void add(int a, int b, int c)
{
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx++;
}

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    //初始g为最大值。
    dist[1] = 0;
		   
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});
    //0是距离，1是点。
   
    while(heap.size()){
        auto t = heap.top();
        heap.pop();
        
        int ver = t.second, distance = t.first;
        
				//因为有的已经加入了queue，然后被标记,所以必须进行st判断。
        if(st[ver]) continue;
        st[ver] = true;
        
        for(int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
								//可加 if(!st[j])
                heap.push({dist[j],j});
								//j有可能访问过，有可能没访问过
            }
        }
    }
    
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main(){
    cin >> n >> m;
    
    memset(h, -1, sizeof h);
    
    while(m --)
    {
        int a, b, c;
        cin >> a >> b >> c; 
        add(a, b, c);
    }
    cout << dijkstra();

    return 0;
}

Bellman-ford

O(mn)，处理负权边，有边数限制的题

循环完n次后，一定满足，dist[b] ≤ dist[a] + w;三角不等式，是一个松弛操作。可处理负权边。

迭代k次，表示的意思是不超过k条边的最短路的距离。

如果存在负权回路，那么就可能不存在最短路径了。

853. 有边数限制的最短路

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 510, M = 100010;
int n, m, k;
int dist[N], backup[N];

struct Edge
{
    int a, b, w;  
}edges[M];

int bellman_ford(){
    
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    for(int i = 0; i < k; ++ i) 
    {
        memcpy(backup, dist, sizeof dist);   
        //需要备份一下，防止多条边或串联问题。
				//因为此题限制最多走k次。
				//如果没有限制，则无需backup
        for(int j = 0; j < m; ++ j)
        {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;   
            dist[b] = min(dist[b], backup[a] + w);
        }
    }
    
    return dist[n];
}

int main(){
    
    cin >> n >> m >> k;
    for(int i = 0; i < m; ++ i)
    {
        int a, b, w;
        cin >> a  >> b >> w;
        edges[i] = {a, b, w};
    }
    
    int t = bellman_ford();
    //t如果大于无穷大，说明没有达到，为什么要除以2？因为无穷大也可能被更新
    if(t > 0x3f3f3f3f / 2) puts("impossible");
    else cout << t;
    return 0;
}

SPFA

不能有负环。

是对Bellman-ford的优化，长得很像Dijkstra算法。

步骤为：

queue ← 1
while queue 不空（仅存放dist减小的）
1. 取出队头，删除队头t
2. 用t去更新所有出边。取min（）
3. 若更新了某个点b，则加入该点入队列。

spfa可能会被卡，需要使用Dijkstra。

spfa判断最短路

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 150010;

int n, m;
int h[N], e[N], ne[N], idx, w[N];
int dist[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx++;
}

int spfa(){
    
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    queue<int> q;
    q.push(1);
    st[1] = true;
    //是否在队列里。
    
    while(q.size())
    {
        int t = q.front();
        q.pop();
        
        st[t] = false;
        
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if(!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
        
    }
    
    return dist[n];
}

int main(){
    cin >> n >> m;
    
    memset(h, -1, sizeof h);
    
    while(m --)
    {
        int a, b, c;
        cin >> a >> b >> c; 
        add(a, b, c);
    }
    int t = spfa();

    if(t == 0x3f3f3f3f) cout << "impossible";
    else cout << t;
    return 0;
}

spfa判断负环

dist[x]表示 1到x的最短距离。
cnt[x] 表示边数。最短路的边数。
- 每次更新dist时(dist[x] > dist[t] + w[i])，更新cnt[x] = cnt[t] + 1;
- 如果cnt[x]出现≥ n的话，那么就比如，=n，那么经过了n条边，一定有n+1个点，一定有两个点是相同的。所以存在负环。

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;

const int N = 2010, M = 10010;

int n,m;
int h[N], w[M], e[M], ne[M], idx;
int dist[N], cnt[N];
bool st[N];

void add(int a ,int b, int c)
{
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx ++;
}

bool spfa()
{
    memset(dist, 0x3f, sizeof dist);    
    queue<int>q;
    
    //因为负环不是从1开始，所以需要所有点都在里面
    for(int i = 1; i <= n; ++ i)
    {
        st[i] = true;
        q.push(i);
    }
    
    while(q.size()){
        int t = q.front();
        q.pop();
        st[t] = false;
        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if(dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];   
                
                cnt[j] = cnt[t] + 1;
                
                if(cnt[j] >= n)
                {
                    return true;
                }
                
                if(!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
        
    }
    return false;
}

int main(){
    cin >> n >> m;
    
    memset(h, -1, sizeof h);
    
    for(int i = 0; i < m; ++ i)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    
    if(spfa()) puts("Yes");
    else puts("No");
    return 0;
}

Floyd

求最短路，基于动态规划

三重循环：d(i, j)存i，j点的距离，k是阶段

k from 1 to n:
1. i form 1 to n：
  1. j from 1 to n
    1. d(i, j) = min( d(i, j), d(i, k) + d(k, j));

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 210, INF = 1e9;
//1e9，由于后面需要d+d，所以不能越界，取1e9
int n, m, Q;

int d[N][N]; //邻接矩阵

void floyd(){
    for(int k = 1; k <= n; ++ k)
        for(int i = 1; i <= n; ++ i)
            for(int j = 1; j <= n; ++ j)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    return;
}

int main(){
    cin >> n >> m >> Q;
    for(int i = 1; i <= n; ++ i)
        for(int j = 1; j <= n; ++ j)
            if( i == j) d[i][j] = 0;
            else d[i][j] = INF;
    while(m--)
    {
        int a, b, w;
        cin >> a >> b >>w;
        d[a][b] = min(d[a][b], w);
    }
    floyd();
    while(Q--)
    {
        int a, b;
        cin >> a >> b;
        if(d[a][b] > INF/2) 
            cout << "impossible" << endl;
        else cout << d[a][b] << endl;
    }
    return 0;
}

最小生成树

对应无向图
Prim算法，普利姆算法
- 类似Dijkstra算法
- 朴素版Prim，对应稠密图 O(n^2)
- 堆优化Prim，对应稀疏图，O(mlogn) ——不常用
Kruskal算法，克鲁斯卡尔算法
- O(mlogm)
- 稀疏图尽量用这个

朴素版的Prim算法

算法流程：

先将所有dist距离初始化为+$\infty$
n次迭代，找到集合外距离集合s中的所有点距离最近的点。（相较于Dijstra算法，Dijstra是距离起点），然后更新其他距离，st[]=true。

可以处理重边和自环，负数权边。

稠密图

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1000, INF = 0x3f3f3f3f;

int n, m;
int g[N][N];
int dist[N];
bool st[N];

int prim(){
    memset(dist, 0x3f, sizeof dist);
    
    int res = 0; //和
    for(int i = 0; i < n ; ++ i)
    {
        int t = -1;
        for(int j = 1; j <= n; ++ j)
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
            
        if(i && dist[t] == INF) return INF; //说明不连通
        
        if(i) res += dist[t];
        //先加再更新，因为有负环，导致dist[t]被更新

        for(int j = 1; j <= n; j ++)
            dist[j] = min(dist[j], g[t][j]);
        
        st[t] = true;
    }
    
    return res;
    
}

int main(){
    scanf("%d%d", &n, &m);
    
    memset(g, 0x3f, sizeof g);
    
    while(m --)
    {
        int a,b,c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);
    } //取最小值
    
    int t = prim();
    
    if (t == INF) puts("impossible");
    else printf("%d\n", t);
    
    return 0;
}

Kruskal

很优美的算法

处理稀疏图

将所有边按照从小到大排序 O(mlogm)
枚举每条边ab，权重为c，如果a和b没有连通，就将c边加入集合中。
1. 需要并查集，时间复杂度是O(1)
2. 总共的复杂度是O(m)

所以复杂度是O(mlogm)，主要在排序。

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 200010;

int n, m;
int p[N];

struct Edge
{
    int a, b, w;
    bool operator<(const Edge &W) const 
    {
        return w < W.w;
    }
    
}edges[N];

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main(){
    cin >> n >> m;
    for(int i = 0; i <m; ++ i)
    {
        int a,b,w ;
        cin >> a >> b >> w;
        edges[i] = {a, b, w};
    }
    
    sort(edges, edges + m);
    
    for(int i = 1; i <= n; ++ i)
        p[i] = i;
    
    int res = 0; int cnt = 0;
    for(int i = 0; i < m; ++ i)
    {
        int a = edges[i].a, b= edges[i].b, w= edges[i].w;
        a = find(a), b = find(b);
        if (a!= b)
        {
            p[a] = b;   
            res += w;
            cnt ++;
        }
    }
    if(cnt < n-1) puts("impossible");
    else printf("%d", res);
    
    return 0;
}

染色法判定二分图

判别一个图是不是二分图。
染色法 O(n + m)

一个图是二分图，当且仅当图中不含奇数环。

图中可能存在重边和自环

二部图又叫二分图，是图论中的一种特殊模型。设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。简单来说，如果图中点可以被分为两组，并且使得所有边都跨越组的边界，则这就是一个二分图。准确地说：把一个图的顶点划分为两个不相交子集，使得每一条边都分别连接两个集合中的顶点。如果存在这样的划分，则此图为一个二分图

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

//稀疏图用邻接表
const int N = 100010, M = 200010;

int n, m;
int h[N], e[M], ne[M], idx;
int color[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

bool dfs(int u, int c)
{
    // cout << u << c << endl;
    color[u] = c;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!color[j])
        {
            if(!dfs(j, 3 -c )) return false;
        }else if(color[j] == c) return false;
    }
    return true;
}

int main(){
    cin >> n >> m;
    memset(h, -1, sizeof h);
    
    while(m --)
    {
        int a, b;
        cin >> a >> b;
        add(a,b), add(b,a);
    }
    
    bool flag = true;
    for(int i = 1; i <= n; ++ i)
    {
        if(!color[i]){
            if(!dfs(i, 1))
            {
                flag = false;
                break;
            }
        }
    }

    if(flag) puts("Yes");
    else puts("No");
    return 0;
}

匈牙利算法

匈牙利算法O(mn)，实际运行时间比较小。

https://www.acwing.com/problem/content/863/

已经是一个二分图，任何一个边必须是两个组的点的连线，求边的最大数量。

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 1010, M = 100010;

int n1, n2, m;
int h[N], e[M], ne[M], idx;

int match[N]; //匹配的点
bool st[N]; 

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

bool find(int x)
{
    for(int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if( !st[j])
        {
            st[j] = true;
            //如果没有match或者match的点有其他的点连。
            if(match[j] == 0 || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}

int main(){
    cin >> n1 >> n2 >> m;
    
    memset(h, -1, sizeof h);
    
    while(m --)
    {
        int a,b;
        cin >> a >> b;
        add(a, b);
    }
    int res = 0;
    for(int i = 1; i <= n1; ++ i)
    {
        memset(st, false, sizeof st);
        if(find(i)) res++;
    }
    cout << res;
    return 0;
}

「Algorithm」03 搜索与图论

DFS和BFS #

DFS： #

BFS #

树和图 #

图的深搜 #

图的广搜 #

848. 有向图的拓扑序列 #

最短路 #

朴素Dijkstra算法 #

堆优化的Dijkstra算法 #

Bellman-ford #

SPFA #

spfa判断最短路 #

spfa判断负环 #

Floyd #

最小生成树 #

朴素版的Prim算法 #

Kruskal #

染色法判定二分图 #

匈牙利算法 #