朝田诗乃 的博客

朝田诗乃 的博客

题解 P2661 【信息传递】

posted on 2018-11-02 16:52:28 | under 题解 |

题意是求有向图中的最小环。用并查集或拓扑排序固然可以搞。但是我们仔细观察一下这个图。n个点,n条边,每个点有且仅有一条出边。

也就是说,每个联通块都构成一棵基环内向树

换句话说,这是一个基环内向树森林。那么,每个联通块内不可能存在两个以上的环。我们从每个联通块的根(入度为零的点)开始dfs,计算联通块中的环的大小。最后计算每个联通块中环的最小值即可。

复杂度 $O(2n)$ 。

#include <cstdio>
int dep[200050], ans = 1e9, next[200050], n, in[200050], vis[200050], tim, flag = 0;
void read(int &x) {
    char ch; while(ch = getchar(), ch < '!');
    x = ch - 48; while(ch = getchar(), ch > '!') x = (x << 3) + (x << 1) + ch - 48;
}
void write(int x) {if(x > 9) write(x/10); putchar(x%10 + 48);}
void dfs(int u) {
    if(dep[next[u]]) {
        if(vis[next[u]] == tim) 
            ans = ans < dep[u] - dep[next[u]] + 1 ? ans : dep[u] - dep[next[u]] + 1;
        return;
    }
    vis[next[u]] = tim; dep[next[u]] = dep[u] + 1;
    dfs(next[u]);
}
int main() {
    read(n);
    for(int i = 1; i <= n; ++i) read(next[i]), ++in[next[i]];
    for(int i = 1; i <= n; ++i)
        if(!in[i]) ++tim, flag = 1, vis[i] = tim, dep[i] = 1, dfs(i);
    flag ? write(ans) : write(n); putchar('\n');
}

代码长度22行。

题解地址→http://www.aknt.top/?p=518