(UVA) 11504 - Dominos [SCC]

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2499

SCC 模板！

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

typedef pair<int,int> pii;
const int MAX_N = 1e5 + 6;

vector<int> edg[MAX_N];
vector<int> rev_edg[MAX_N];
int stamp[MAX_N];
int in_scc[MAX_N];
int rudu[MAX_N];
bool visit[MAX_N];

void dfs_for_stamp(int id,int &cur_depth) {
    visit[id]=true;
    for (auto i=rev_edg[id].begin();i!=rev_edg[id].end();i++) {
        int tmp=*i;
        if (visit[tmp]==false) dfs_for_stamp(tmp,cur_depth);
    }
    stamp[cur_depth++]=id;
}

void dfs_for_scc(int id,int scc) {
    visit[id]=true;
    for (auto i=edg[id].begin();i!=edg[id].end();i++) {
        int tmp=*i;
        if (visit[tmp]==false) {
            dfs_for_scc(tmp,scc);
        }
    }
    in_scc[id]=scc;
}

int main () {
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
    int T;
    scanf("%d",&T);
    while (T--) {
        int n,m;
        scanf("%d %d",&n,&m);
        for (int x=0;n>=x;x++) {
            edg[x].clear();
            rev_edg[x].clear();
            stamp[x]=in_scc[x]=rudu[x]=0;
            visit[x]=false;
        }
        for (int x=0;m>x;x++) {
            int i,j;
            scanf("%d %d",&i,&j);
            edg[i].push_back(j);
            rev_edg[j].push_back(i);
        }
        int cur_depth=1;
        for (int x=1;n>=x;x++) {
            if (visit[x]==false) dfs_for_stamp(x,cur_depth);
        }
        for (int x=1;n>=x;x++) {
            visit[x]=false;
        }
        int scc=1;
        for (int x=n;x>=1;x--) {
            if (visit[stamp[x]]==false) {
                dfs_for_scc(stamp[x],scc++);
            }
        }
        for (int x=1;n>=x;x++) {
            for (auto i=edg[x].begin();i!=edg[x].end();i++) {
                int tmp=*i;
                if (in_scc[x]!=in_scc[tmp]) rudu[in_scc[tmp]]++;
            }
        }
        int ans=0;
        for(int x=1;scc>x;x++) {
            if (rudu[x]==0) ans++;
        }
        printf("%d\n",ans);
    }
}