洛谷 P2661 信息传递（NOIP 提高 2015）

电玩女神 2021-11-16 06:42 274阅读 0赞

### [传送门][Link 1] ###

#### 本题本来是一个很好的并查集的题（似乎靠的就是并查集），然而蒟蒻我刚刚学习了 ####

#### tarjan 所以就用 terjan做了一下 ####

大概题意就是：一个人要和另外的一个人告诉他所知道的信息，然后问什么时候他自己的生日可以由  
一个人那里传回自己这里来。  
那么这个一个人向另一个人传递信息，我们可以看成一条有向边。  
因为是问什么时候自己的信息可以传回自己这里，  
可以自己yy成，一个有向边的环（因为成为一个环，才可以传回自己这里），  
那么因为答案求的是有人知道就停止，  
那么则是求一个最小的环，所以我们可以求一个图的强连通分量。  
因为这个图有解，而且这个图每个点只有一个出度，  
那么图一定会构成一个环，那么我们求的时候，  
求出每一个环的长度，然后更新一下ans值就行了。

### 来， 上代码。 ###

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    #include <iomanip>
    #include <cstdlib>
    #define N 20000010
    
    using namespace std;
    bool vis[N];
    int s[N], dfn[N], siz[N], low[N], to[N], bl[N];
    int top, cnt, tmp, n;
    int ans = 0x7fffffff;
    int read() {
        int s = 0, f = 0; char ch = getchar();
        while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
        while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
        return f ? -s : s;
    }
    
    void tarjer(int u) {
        vis[u] = true;
        s[++top] = u;
        dfn[u] = low[u] = ++cnt;
        if (! dfn[to[u]]) {
            tarjer(to[u]);
            low[u] = min(low[to[u]], low[u]);
        }
        else if (vis[to[u]]) low[u] = min(low[u], dfn[to[u]]);
        if (dfn[u] == low[u]) {
            tmp = 0;
            while (s[top] != u) vis[s[top--]] = false, tmp++;
            tmp++, top--;
            bl[u] = u;
            if (tmp > 1) ans = min(ans, tmp); 
        }
    }
    
    int main() {
        n = read();
        for (int i = 1, a; i <= n; i++) a = read(), to[i] = a;
        for (int i = 1; i <= n; i++) tarjer(i);
        cout << ans;
    }

看了这么多，不留个赞再走嘛？

转载于:https://www.cnblogs.com/zzz-hhh/p/11215333.html

[Link 1]: https://www.luogu.org/problemnew/show/P2661