Uva(12167)(Proving Equivalences)

链接：https://vjudge.net/problem/UVA-12167
思路：强连通分量+缩点。最后统计出度和入度为0的点，取最大值即可
代码：

#include<cstdio>
#include<deque>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;

struct edge{
    int u,v;
    edge(){}
    edge(int uu,int vv):u(uu),v(vv){}
};

const int maxn = 20001;
int t,n,m;
vector<int> G[maxn];
int dfn[maxn],low[maxn],sccno[maxn],in[maxn],out[maxn];
int ntime,bcc_cnt;
deque<int> P;

void tarjan(int u){
    dfn[u] = low[u] = ++ntime;
    P.push_back(u);
    for(int i=0;i<G[u].size();i++){
        int v = G[u][i];
        if(!dfn[v]){
        tarjan(v);
        low[u] = min(low[u],low[v]);
        }
        else if(!sccno[v]){
            low[u] = min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u]){
        bcc_cnt++;
        int tmp;
        do{
            tmp = P.back();
            P.pop_back();
            sccno[tmp] = bcc_cnt;//一个强连通分量里面的点属于一个缩点的编号
        }while(tmp!=u);
    }
}

void find_bcc(int n){
    memset(sccno,0,sizeof(sccno));
    memset(dfn,0,sizeof(dfn));
    ntime = bcc_cnt = 0;
    for(int i=0;i<n;++i)if(!dfn[i])tarjan(i);
}

int main(){
    scanf("%d",&t);
    while(t--){
        for(int i=0;i<n;++i)G[i].clear();
        scanf("%d%d",&n,&m);
        for(int i=0;i<m;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            a--;
            b--;
            G[a].push_back(b);
        }
        find_bcc(n);
        for(int i=1;i<=bcc_cnt;i++)in[i] = out[i] = 1;
            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])
                                        in[sccno[v]] = out[sccno[u]] = 0;//如果u，v不属于一个强连通分量，那么u的出度不为0，v的入度不为0！！
                }
                int a = 0,b=0;
                for(int i=1;i<=bcc_cnt;i++){
                    if(in[i])a++;
                    if(out[i])b++;
                }
                int ans = max(a,b);
                if(bcc_cnt==1)ans = 0;
                printf("%d\n",ans);
    }
    return 0;
}