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

传送门

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

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

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