搜索与图论

Created in March 13, 2025

2025   ·   code   algorithm   acwing   搜索与图论   ·   learning-notebook

DFS

数字排列问题

#include <bits/stdc++.h>

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 < u; i ++){
            cout << path[i] << " ";
        }
        cout << endl;
        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皇后问题

Snipaste_2024-12-21_18-27-53.png

解题思路

  • 和排列数字相同，只不过这次在一行数字中进行排列的是皇后所在的行号，例如：123表示
Q    
  Q  
    Q
  • 注意剪枝
    • 如果能过提前判断一个方案不合法，那么就提前中止递归

代码实现

第一种搜索顺序

  • 对于同一列不能有多个皇后，我们设定数组col[n]来记录每列中含有皇后的状态
  • 对于对角线不能有多个皇后，我们设定数组dg[n]来记录每个对角线中含有皇后的状态
    • 在使用时，我们利用一次函数截距为常量的性质，来保证每个正对角线中只含有一个皇后
    • 例如：\(y = - x + b \rightarrow b = y + x\)\(y =x+b\rightarrow b = y -x\)由于$k >0$时可能导致数组下标为负，那么就需要添加一个足够大的常量保证其为正
  • 对于反对角线不能有多个皇后，我们设定数组udg[n]来记录每个反对角线中含有皇后的状态

    • 使用时为udg[u - i + n] 

#include <bits/stdc++.h>
using namespace std;

const int N = 20;
int n;
char g[N][N];
int col[N], dg[N], udg[N];

void dfs(int u){

    if(u == n){
        for(int i = 0; i < n; i ++){
            cout << g[i] << endl;
        }
        cout << endl;
        return ;
    }

    for(int i = 0; i < n; i ++){
        if(!col[i] && !dg[i + u] && !udg[i - u + n]){
            g[u][i] = 'Q';
            col[i] = dg[i + u] = udg[i - u + n] = true;
            dfs(u + 1);
            g[u][i] = '.';
            col[i] = dg[i + u] = udg[i - u + n] = false;
        }
    }
}

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;
}

第二种搜索顺序

#include <bits/stdc++.h>
using namespace std;

const int N = 20;
int n;
char g[N][N];
int row[N], col[N], dg[N], udg[N];

void dfs(int x, int y, int s){

    if(y == n){
        y = 0;
        x ++;
    }

    if(x == n){
        if(s == n){
            for(int i = 0; i < n; i ++){
                puts(g[i]);
            }
            cout << endl;
        }
        return ;
    }

    // 不放皇后
    dfs(x, y + 1, s);

    // 放皇后
    if(!row[x] && !col[y] && !dg[x + y] && !udg[n + x - y]){
        g[x][y] = 'Q';
        row[x] = col[y] = dg[x + y] = udg[n + x - y] = true;
        dfs(x, y + 1, s + 1);
        g[x][y] = '.';
        row[x] = col[y] = dg[x + y] = udg[n + x - y] = false;
    }
}

int main(){
    cin >> n;


    for(int i = 0; i < n; i ++){
        for(int j = 0; j < n; j ++){
            g[i][j] = '.';
        }
    }

    dfs(0, 0, 0);

    return 0;
}

BFS

走迷宫

算法思路

  • 利用
  • 只有边权路都是1时，才可以用BFS求最短路

实现代码

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
const int N = 110;
int n, m;
int g[N][N];
int d[N][N];
PII q[N * N];

int bfs(){
    int hh = 0, tt = 0;
    q[0] = {0, 0};
    memset(d, -1, sizeof d);
    d[0][0] = 0;
    // 从迷宫的左上角出发

    int dx[4] = {-1, 0, 1, 0};
    int 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];
            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;
                q[ ++ tt] = {x, y};
            }
        }

    }

    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;

}

八数码

解题思路

  • 求把数字变为正常顺序的最小步数

困难

  • 三个问题需要解决：
    • 状态表示复杂
    • 如何记录每个状态的距离
      • 可以将状态定义为一个字符串

记录状态

  • 将每个状态定义为一个字符串
1 2 3
4 5 6
7 8 x
  • 例如上面这个字符串就可以记录为12345678x
  • 定义queue<string> queue和unordered_map<string, int> dst用于求解

状态转移

  • 记录状态转移过程总共分三步
    • 首先把字符串恢复成3*3的样子
    • 移动，进行状态转移，枚举上下左右
    • 将移动后的3*3恢复成字符串

解题代码



#include <bits/stdc++.h>

using namespace std;

int bfs(string start){

    queue<string> q;
    unordered_map<string, int> d;

    q.push(start);
    d[start] = 0;

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
    string end = "12345678x";
    while(q.size()){

        auto t = q.front();
        q.pop();

        if(t == end)
            return d[t];

        int distance = d[t];

        int k = t.find('x');
        int x = k / 3, y = k % 3;

        for(int i = 0; i < 4; i ++){
            int a = x + dx[i], b = y + dy[i];

            if(a >= 0 && a < 3 && b >= 0 && b < 3){
                swap(t[k], t[a * 3 + b]);

                if(!d.count(t)){
                    // 如果这种状态之前一次也没有出现过，那么就将其入队，并记录其距离
                    	// Searches the container for elements whose key is _k_ and returns the number of elements found. Because [unordered_map](https://cplusplus.com/unordered_map) containers do not allow for duplicate keys, this means that the function actually returns 1 if an element with that key exists in the container, and zero otherwise.
                    d[t] = distance + 1;
                    q.push(t);
                }

                swap(t[k], t[a * 3 + b]);
            }
        }
    }

    return -1;
}

int main(){
    string start;
    for(int i = 0; i < 9; i ++){
        char c;
        cin >> c;
        start += c;
    }

    cout << bfs(start) << endl;
    return 0;
}

树与图的深度优先遍历

树和图的存储

  • 由于树就是一种特殊的图，所以这里我们直接讨论图的存储方式
  • 图分为：
    • 有向图：$a \rightarrow b$
    • 无向图：$a - b$
      • 其实无向图可用$a \rightarrow b$和$b \rightarrow a$来表示
  • 所以我们再次简化，只讨论有向图的存储方式：
    • 邻接矩阵：开个二维数组
      • 用g[a][b]来表示$a\rightarrow b$
      • 如果有权重$w$，那么g[a][b] = w
      • 如果没有权重，那么g[a][b] = 1，单纯存储一个bool值
    • 邻接表：开$N$个单链表
      • $N$个点，每个点对应一个单链表
      • 每个单链表中存储的是与该点连接
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 100, M = 2 * N;

int h[N], e[M], ne[M], idx;

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


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

树和图的深度优先搜索

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 100, M = 2 * N;
int n, m;
int h[N], e[M], ne[M], 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(){
  int n;
  cin >> n;
  dfs(1);
  return 0;
}

树的重心

知识点

解题思路

  • 我们需要找到删去每个结点之后各个连通块中的点数的最大值
  • 可以使用深度优先遍历去看每个点的子树的大小，然后使用总的点数减去子树大小，就可以获得另一连通块中点的数量

实现代码


#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 100, M = 2 * N;
int h[N], e[M], ne[M], idx, n;
int ans = N;
bool st[N];

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

int dfs(int u){
    st[u] = true;
    // size是res，表示的是把这个点删掉之后，每一个连通块大小的最大值
    // sum用来记录当前子树的大小
    int size = 0, sum = 0;
    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if(st[j])
            continue;

        int s = dfs(j);
        // 将这个点删除之后，这个点的每个子树都成为一个连通块了
        size = max(size, s);
        sum += s;

    }

    // 还要包含子树的头结点
    size = max(size, n - sum - 1);
    ans = min(ans, size);

    return sum + 1;
}


int main(){
    // int n;
    cin >> n;
    memset(h, -1, sizeof h);
    for(int i = 0; i < n - 1; i ++){
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        add(b, a);
    }

    dfs(1);

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

树与图的广度优先遍历

图中点的层次

知识点

解题思路

  • 第一个宽搜到的路径一定是最短的路径，直接返回就可以
  • 使用队列存储每一层节点

实现代码


#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 100;
int h[N], e[N], ne[N], idx;
// bool st[N];
int n, m;
int d[N];

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

int bfs(){
    memset(d, -1, sizeof d);
    queue<int> q;
    d[1] = 0;
    q.push(1);
    while(q.size()){
        int t = q.front();
        q.pop();
        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];

            if(d[j] == -1){
                d[j] = d[t] + 1;
                q.push(j);
            }
        }
    }

    return d[n];
}


int main(){
    cin >> 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);
    }

    cout << bfs() << endl;

    return 0;
}

Dijkstra

Dijkstra求最短路1

算法思想

  1. 初始化距离，dist[1] = 0, dist[i] = inf；初始化集合s，当前已确定最短距离的点
  2. for i: 0 ~ ni从0~n进行迭代
    • 找到不在s中，距离当前结构最近的点t
    • 把这个点t加到s中
    • 用t更新其他点的距离，即从a点到b点的路径中，由于t的加入，产生了新的路径，如果这个新的路径的距离更短，那么就要更新a点和b点之间最短路径的距离，其实就是判断dist[x] > dist[t] + w
  • 稠密图用邻接矩阵存储
  • 稀疏图用邻接表存储

实现代码

#include <bits/stdc++.h>

using namespace std;

const int N = 510;

int n, m;
int g[N][N];
int dist[N];
// st[i]表示第i个点有没有确定最短路，即这个点是否在集合中
bool st[N];

int dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for(int i = 1; i <= n; i ++){
        int t = -1;
        // 这个点t代表已经成图集合中距离原点最近的点，最开始赋值为-1表示还没有初始化没有找到
        // 此处t=-1表示当前没在集合中，距离集合最近的点还没找到
        for(int j = 1; j <= n; j ++ ){
            if(!st[j] && (t == -1 || dist[t] > dist[j])){
                // 此处代表两种情况
                // 第一种情况为t = -1表示还没在集合中
                // 第二种情况为dist[t] > dist[j]，表示当前的距离还不是最短的，需要更新
                t = j;
            }
        }

        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(void){

    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);
    }
    int t = dijkstra();
    cout << t << endl;
    return 0;
}

Dijkstra求最短路2

知识点

解题思路

  • 使用最小堆维护，可以在常数级别找到已经连通集合中距离散点集合最近的点
  • 找到点后，判断该点是否已经被遍历过
    • 如果遍历过则继续进行循环
    • 如果没被遍历过则更新dist[]数组
  • 直至最小堆中没有任何元素
  • 迭代n - 1次，因为上来就选中了一个点

实现代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 100;
int h[N], w[N],e[N], ne[N], idx;
bool st[N];
int n, m;
int dist[N];

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

int dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> q;
    // 优先队列中存储的是pair类型
    // pair的首元素存储的是原点到该点的距离，因为需要小根堆根据距离进行排序
    // pair的次元素存储的是该点的编号
    q.push({0, 1});

    while(q.size()){
        auto t = q.top();
        q.pop();
        //
        int ver = t.second;
        int distance = t.first;

        if(st[ver])
            continue;
        st[ver] = true;

        for(int i = h[ver]; i != -1; i = ne[i]){
            int j = e[i];
            if(dist[j] > dist[ver] + w[i]){
                dist[j] = dist[ver] + w[i];
                q.push({dist[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;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }


    cout << dijkstra() << endl;

    return 0;
}

bellman-ford

有边数限制的最短路

知识点

  • 只要存在负权边，那么就不能使用Dijkstra算法

解题思路

  • 循环n次
  • 在每次循环中，对于每条边a, b, w，对距离进行更新\(\text{dist}[b]=\min (\text{dist}[b], \text{dist}[a]+w)\)
  • 对于实施BF算法后的
  • 比如当前迭代了k次
    • 从1号点经过不超过k条边，到了另一点的最短路径
    • 如果迭代了n次，那么说明这条路径上有n条边，即这条路径上有n + 1个点；给定一共有n个点，根据抽屉原理，则该条路径一定有两个相同点，即存在回路
    • 所以，如果第n次迭代进行了更新，就说明存在一条边数为n的路径，就说明存在负环

实现代码

#include <bits/stdc++.h>
using namespace std;

const int N = 510, M = 10010;
struct Edge{
    int a, b, w;
}edges[M];

int dist[N];
int last[N];
int n, m, k;

void bellmanford(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for(int i = 0; i < k; i ++){
        memcpy(last, dist, sizeof dist);

        for(int j = 0; j < m; j ++){
            auto e = edges[j];
            dist[e.b] = min(dist[e.b], last[e.a] + e.w);
        }
    }
}


int main(){
    cin >> n >> m >> k;
    for(int i = 0; i < m; i ++){
        // auto e = edges[i];
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        edges[i] = {a, b, w};
    }


    bellmanford();


    if(dist[n] > 0x3f3f3f3f / 2)
        cout << "impossible" << endl;
    else
        cout << dist[n] << endl;

    return 0;
}

spfa

spfa求最短路

知识点

解题思路

  • 改进版的bellman-ford算法
  • 对于更新的距离的端点，即使用到下列公式的点，将其入队\(\text{dist}[b]=\min (\text{dist}[b], \text{dist}[a]+w)\)
  • 当队列不空时，进行遍历：
    • 将队头出队，并赋值给t
    • 更新t的所有出边，对于更新的出边的另一端端点b，我们将其入队

实现代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 100;
int h[N], e[N], ne[N], w[N], idx;
int n, m;
int dist[N];
bool st[N];

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


int spfa(){
    memset(dist, 0x3f, sizeof dist);

    dist[1] = 0;
    queue<int> q;
    q.push(1);
    while(!q.empty()){
        int t = q.front();
        q.pop();
        st[t] = false;
        for(int i = h[t]; i != -1; i = ne[i]){
            // i就是idx
            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;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }


    int t = spfa();

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

    return 0;
}

spfa判断负环

知识点

解题思路

  • dist[x]最短距离
  • cnt[x]当前最短路的边数
  • 更新方式
dist[x] = dist[t] + w[t];
cnt[x] = cnt[t] + 1;

实现代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 100;
int h[N], w[N], e[N], ne[N], idx;
int n, m;
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(){
    queue<int> q;
    for(int i = 1; i <= n; i ++){
        st[i] = true;
        q.push(i);
    }

    while(!q.empty()){
        int t = q.front();
        q.pop();

        // 如果这个点从队列中出队了
        // 那么为了之后的遍历
        // 需要将其访问状态设置为false
        // 才能够让之后的结点访问
        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);
    while(m --){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    if(spfa())
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}

Floyd

Floyd求最短路

知识点

解题思路

  • 使用动态规划解决这个问题，因为所有点都已经在图中
  • 或许还需要深入理解……

实现代码

#include <bits/stdc++.h>
using namespace std;

const int N = 210, INF = 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]);
            }
        }
    }
}

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, c;
        scanf("%d%d%d", &a, &b, &c);
        d[a][b] = min(d[a][b], c);
    }

    floyd();

    while(Q --){
        int a, b;
        scanf("%d%d", &a, &b);
        int t = d[a][b];
        if(t > INF / 2)
            cout << "impossible" << endl;
        else
            cout << t << endl;
    }
}

Prim

Prim算法求最小生成树

知识点

解题思路

朴素Prim算法

  • 首先将数组dist[]初始化为$+\infty$
  • 进行n次迭代
    • 因为需要选取n个点
    • 找到集合外距离最近的点，并将其赋值给t
    • 用t更新其他点到集合的距离（与Dijkstra算法进行区分！）
      • 看一个生成树外的点有没有边连向集合内部的边，并找出最短的那条边
    • s[t] = true
  • 构成最小生成树的边就是每次点t连接最小生成树的那条边，树有多条这种边构成的

实现代码

#include <bits/stdc++.h>
using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

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

int prim(){
    memset(dist, 0x3f, sizeof dist);

    int res = 0;
    for(int i = 0; i < n; i ++){
        // 将i从0开始，可以自动初始化选择第一个点
        // 如果从1开始，需要将数组dist[1]赋值为0
        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];

        st[t] = true;

        for(int j = 1; j <= n; j ++)
            dist[j] = min(dist[j], g[t][j]);

    }
    return res;
}

int main(){
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    while(m --){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = g[b][a] = min(g[a][b], c);
    }


    int t = prim();
    if(t == INF)
        cout << "impossible" << endl;
    else
        cout << t << endl;

    return 0;
}

Kruskal

Kruskal算法求最小生成树

知识点

解题思路

  • 将所有边按权重从小到大进行排序（算法瓶颈$\Omega(m\log m)$）
  • 枚举每条边ab，权重为c（类似于并查集，时间复杂度为$\Omega(m)$）
    • 如果ab不联通，将ab这条边加入集合中
    • 使用并查集来判断两个点之间有没有边，即两个点在不在同一集合当中

实现代码

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 100, INF = 0x3f3f3f3f;

int p[N];
int n, m;

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

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

int kruskal(){
    sort(edge, edge + m);
    for(int i = 1; i <= n; i ++)
        p[i] = i;


    int res = 0, cnt = 0;

    for(int i = 0; i < m; i ++){
        int a = edge[i].a, b = edge[i].b, w = edge[i].w;

        a = find(a), b = find(b);
        if(a != b){
            res += w;
            cnt ++;
            p[a] = b;
        }
    }

    if(cnt < n - 1)
        return INF;
    return res;
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < m; i ++){
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        edge[i] = {a, b, w};
    }

    int t = kruskal();

    if(t == INF)
        cout << "impossible"  << endl;
    else
        cout << t << endl;

    return 0;



}

染色法判定二分图

染色法判定二分图

知识点

  • 二分图当且仅当图中不含奇数环
    • 充分性证明：由于图中不含奇数环，所以染色过程中一定没有矛盾
    • 必要性证明：
    • 可以把所有点划分到两边去
  • 奇数环：环当中边的数量是奇数

解题思路

  • 染色法
for(int i = 1; i <= n; i ++){
    if i未染色
        dfs(i);
}

实现代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 100, M = 2 * N;

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

bool 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] == 0){
            if(!dfs(j, 3 - c))
                return false;
        }
        else if(color[j] == c)
            return false;
    }

    return true;
}

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

int main(){
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while(m --){
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        add(b, a);
    }

    bool flag = true;
    for(int i = 1; i <= n; i ++){
        if(color[i] == 0){
            if(!dfs(i, 1)){
                flag = false;
                break;
            }
        }
    }

    if(flag)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}

匈牙利算法

二分图的最大匹配

知识点

解题思路

实现代码

#include <bits/stdc++.h>
using namespace std;
const int N = 510, M = 1e5 + 100;

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

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] == false){
            st[j] = true;
            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;
        scanf("%d%d", &a, &b);
        add(a, b);
    }

    int res = 0;
    for(int i = 1; i <= n1; i ++){
        // 需要将st数组设置为false，来让抢夺端点可行下去
        // 如果一个人来抢夺端点，发现已经为true，那么将直接跳过
        // 如果没有初始化为false
        memset(st, false, sizeof st);
        if(find(i))
            res ++;
    }

    cout << res << endl;
    return 0;
}


Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • Google Gemini updates: Flash 1.5, Gemma 2 and Project Astra
  • Displaying External Posts on Your al-folio Blog
  • 强化学习导论
  • 企业项目实训
  • 面试总结