(IOIcamp_Judge) 27. 骨牌 [SCC]

http://judge.ioicamp.org/problems/29
https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2499
Zj上面也有

就是你要把SCC壓成一個點，然後不斷去找入度=0的點，就好了

求SCC：
1. 把圖反向
2. topological sort反向圖，紀錄time tag
3. 從time tag最大的開始dfs SCC

這裡 是另外一邊一模一樣的

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

const int MAX_N = 100003;

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

vector<int> sccedg[MAX_N];
int rudu[MAX_N];
int chudu[MAX_N];

void dfs_for_stamp(int now,int& cur_stamp) {
//    cout<<"in "<<now<<endl;
    visit[now]=true;
    int len=rev_edg[now].size();
    for (int x=0;len>x;x++) {
        int i=rev_edg[now][x];
        if (visit[i]==false) {
            dfs_for_stamp(i,cur_stamp);
        }
    }
    who_get_stamp[cur_stamp++] = now;
}

void dfs_for_scc(int now,int scc) {
    visit[now]=true;
    int len=edg[now].size();
    for (int x=0;len>x;x++) {
        int i=edg[now][x];
        if (visit[i]==false) {
            dfs_for_scc(i,scc);
        }
    }
    in_scc[now]=scc;
}

int get_scc(int n) {
    
    memset(who_get_stamp,-1,sizeof(who_get_stamp));
    for (int x=0;n>=x;x++) visit[x]=false;
    int cur_stamp=1;
    for (int x=1;n>=x;x++) {
        
        if (visit[x]==false) {
            dfs_for_stamp(x,cur_stamp);
        }
    }
    for (int x=0;n>=x;x++) visit[x]=false;
    int scc=0;
    for (int x=n;x>=1;x--) {
        if (visit[who_get_stamp[x]]==false) {
            dfs_for_scc(who_get_stamp[x],scc++);
        }
    }
//    for (int x=1;n>=x;x++) cout<<"scc["<<x<<"] = "<<in_scc[x]<<endl;
    for (int x=0;scc>x;x++) {
        sccedg[x].clear();
        rudu[x]=chudu[x]=0;
    }
//    puts("in");
//    cout<<"scc="<<scc<<endl;
    for (int i=1;n>=i;i++) { //restore edge
        int len=edg[i].size();
        for (int j=0;len>j;j++) {
            int x=edg[i][j];
            if (in_scc[i]==in_scc[x]) continue;
            sccedg[in_scc[i]].push_back(in_scc[x]);
            rudu[in_scc[x]]++;
            chudu[in_scc[i]]++;
        }
    }
    
    int ans=0;
    //topological sort
    for (int i=0;scc>i;i++) {
        if (rudu[i]==0) ans++;
    }
    return ans;
}

int main () {
    int T;
    scanf("%d",&T);
    for (int qq=1;T>=qq;qq++) {
        int n,m;
        scanf("%d %d",&n,&m);
        for (int x=1;n>=x;x++) edg[x].clear();
        for (int x=1;n>=x;x++) rev_edg[x].clear();
        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);
        }
        printf("%d\n",get_scc(n));
    }
}