一道强连通分量的裸题。

由题意,对于唯一出度为0的的强连通分量,我们可以认为其中所有的奶牛均是明星奶牛,而若存在两个出度为0的强连通分量则不存在明星奶牛。

我们通过Tarjan算法计算出强连通分量,对每个强连通分量进行染色并计算出度。

参考代码:

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

const int N = 50001;

int n, m;
int ind, gid;
int g[N], gn[N];
int low[N], dfn[N];
int ext[N];
bool instack[N];
stack<int> s;
vector<int> G[N];

int min(int a, int b) {
    return a < b ? a : b;
}

void tarjan(int u) {
    low[u] = dfn[u] = ++ind;
    instack[u] = true;
    s.push(u);
    
    for ( auto v : G[u] ) {
        if ( !dfn[v] ) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if ( instack[u] )
            low[u] = min(low[u], dfn[v]);
    }

    if ( low[u] == dfn[u] ) {
        ++gid;
        int cur;
        do {
            cur = s.top();
            g[cur] = gid;
            ++gn[gid];
            instack[cur] = false;
            s.pop();
        } while ( cur != u );
    }
}

int main() {
    ios::sync_with_stdio(false);

    cin >> n >> m;

    int u, v;
    for ( int i = 1; i <= m; ++i ) {
        cin >> u >> v;
        G[u].push_back(v);
    }

    for ( int i = 1; i <= n; ++i ) 
        if ( !dfn[i] ) 
            tarjan(i);

    for ( int u = 1; u <= n; ++u ) {
        for ( auto v : G[u] )
            if ( g[v] != g[u] )
                ++ext[g[u]];
    }

    int ans = 0;
    for ( int i = 1; i <= gid; ++i )
        if ( !ext[i] ) {
            if ( ans ) {
                cout << 0 << endl;
                
                return 0;
            }

            ans = gn[i];
        }

    cout << ans << endl;

    return 0;
}
Last modification:January 18th, 2020 at 04:42 pm
博客维护不易,如果你觉得我的文章有用,请随意赞赏