P8287

我是逍逍 · 2022-05-26 21:55:06 · 题解

题目大意

在一个由 n 个点，m 条边组成的无向图中有 k 个源点，每个源点的流扩散速率都为 1 ，求最早形成简单环的时间。

吐槽

一看到环，立刻就想到了 Tarjan 算法，但是不知为何打炸了，也没有在题解里看到类似的做法（没看懂），如有解法，欢迎留言赐教。

算法概述

使用广搜模拟扩散过程，使用并查集维护扩散源关系：

• 若某一已扩散节点 x 与带扩散节点 y 同属于一个集合中，则此次扩展已经成环，统计答案。
• 若不满足条件，则将 x 与 y 所在集合合并，为未来统计答案做准备。
• 特别的，如果数据为树形结构，即 m = n - 1 ，那么可以直接判定无解。由于题目保证图联通，因此其它情况均有解。

搜索过程中，记录 dis_x 表示节点 x 与其最近的源点的距离， vis_x 表示节点 x 是否已经扩展过， f_x 记录节点 x 所在的集合编号。
注：此题的输入数据量较大，建议使用快读，下方代码中使用 sync_with_stdio(false) 关闭流同步，勉强能过。

代码

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
const int Max = 1000005;

int n, m, k, ans = Max, f[Max], dis[Max];
vector<int> g[Max];
queue<pair<int, int>> q;
bool vis[Max];

int father(int x) { // 并查集 
    if (f[x] == x)
        return x;
    return f[x] = father(f[x]);
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m >> k;

    if (m == n - 1) { // 判定无解 
        cout << "Poor D!" << endl;
        return 0;
    }
    for (int i = 1; i <= n; i++) // 并查集初始化 
        f[i] = i;

    for (int i = 1, x, y; i <= m; i++) {
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    for (int i = 1, x; i <= k; i++) {  
        cin >> x;
        q.push(make_pair(x, 0)); // 搜索由 k 个源点同时开始 
        dis[x] = 1;
    }

    while (!q.empty()) {
        int x = q.front().first; // 当前节点 
        int fa = q.front().second; // 父节点 
        q.pop();
        if (vis[x])  
            continue;
        vis[x] = true;

        for (auto y: g[x]) 
            if (y != fa) { // 跳过父节点 
                if (!dis[y]) {
                    dis[y] = dis[x] + 1;
                    q.push(make_pair(y, x));
                    f[father(y)] = father(x);
                } else if (!(dis[y] + 1 == dis[x] || (vis[y] && dis[y] == dis[x]))) {
                    if (father(y) == father(x)) // 已经同属一个集合 统计答案 
                        ans = min(max(dis[y], dis[x]) - 1, ans);
                    else
                        f[father(y)] = father(x);
                }
            }
    }

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