hdu2767 Proving Equivalences，有向图强联通，Kosaraju算法

点击打开链接

有向图强联通，Kosaraju算法

缩点后分别入度和出度为0的点的个数 answer = max(a, b);

scc_cnt = 1; answer = 0

#include<cstdio>

#include<algorithm>

#include<vector>

#include<cstring>

#include<stack>

using namespace std;

const int maxn = 20000 + 10;

vector<int> G[maxn], G2[maxn];

vector<int> S;

int vis[maxn], sccno[maxn], scc_cnt;

void dfs1(int u){

    if(vis[u]) return ;

    vis[u] = 1;

    for(int i=0; i<G[u].size(); ++i) dfs1(G[u][i]);

    S.push_back(u);

}

void dfs2(int u){

    if(sccno[u]) return ;

    sccno[u] = scc_cnt;

    for(int i=0; i<G2[u].size(); ++i)dfs2(G2[u][i]);

}

void find_scc(int n){

    scc_cnt = 0;

    S.clear();

    memset(sccno, 0, sizeof sccno );

    memset(vis, 0, sizeof vis );

    for(int i=0; i<n; ++i) dfs1(i);

    for(int i=n-1; i>=0; --i){

        if(!sccno[S[i]]) {

            scc_cnt++;

            dfs2(S[i]);

        }

    }

}

int in[maxn], out[maxn];

int main(){

    int T, n, m;

    scanf("%d", &T);

    while(T--){

        scanf("%d%d", &n, &m);

        for(int i=0; i<n; ++i) {

            G[i].clear(); G2[i].clear();

        }

        for(int i=0; i<m; ++i){

            int u, v;

            scanf("%d%d", &u, &v); u--; v--;

            G[u].push_back(v);

            G2[v].push_back(u);

        }

        find_scc(n);

        if(scc_cnt==1){

            printf("0\n");

            continue;

        }

        memset(in, 0, sizeof in );

        memset(out, 0, sizeof out );

        for(int u=0; u<n; ++u){

            for(int i=0; i<G[u].size(); ++i){

                int &v = G[u][i];

                if(sccno[u] != sccno[v]) {

                    out[sccno[u]]++;

                    in[sccno[v]]++;

                }

            }

        }

        int a = 0, b = 0;

        for(int i=1; i<=scc_cnt; ++i){

            if(!in[i]) a++;

            if(!out[i]) b++;

        }

        printf("%d\n", max(a, b));

    }

    return 0;

}