POJ1236 Network of Schools

PS: 强连通，缩点。注意不要忘记考虑图是强连通的情况，WA了4次。省赛热身。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
using namespace std;
const int maxn = 110;

vector<int> G[maxn];
vector<int> G1[maxn];
vector<int> RG1[maxn];
int n;

int low[maxn], pre[maxn], sccno[maxn];
int dfs_clock, scc_cnt;
stack<int> S;

void dfs(int u) {
    low[u] = pre[u] = ++dfs_clock;
    S.push(u);
    for(int i = 0; i < (int)G[u].size(); i++) {
        int v = G[u][i];
        if(!pre[v]) {
            dfs(v);
            low[u] = min(low[u], low[v]);
        } else if(!sccno[v]) {
            low[u] = min(low[u], low[v]);
        }
    }
    if(pre[u]==low[u]) {
        scc_cnt++;
        for(;;) {
            int x = S.top(); S.pop();
            sccno[x] = scc_cnt;
            if(x==u) break;
        }
    }
}

void find_scc() {
    while(!S.empty()) S.pop();
    memset(sccno, 0, sizeof(sccno));
    memset(pre, 0, sizeof(pre));
    memset(low, 0, sizeof(low));
    scc_cnt = 0; dfs_clock = 0;
    for(int i = 1; i <= n; i++) {
        if(!pre[i]) dfs(i);
    }
}

void build_DAG() {
    int s, t;
    for(int i = 1; i <= scc_cnt; i++) {
        G1[i].clear();
        RG1[i].clear();
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < (int)G[i].size(); j++) {
            int v = G[i][j];
            s = sccno[i]; t = sccno[v];
            if(s!=t) {
                G1[s].push_back(t);
                RG1[t].push_back(s);
            }
        }
    }
}
void work() {
    int ans1 = 0, ans2 = 0;
    for(int i = 1; i <= scc_cnt; i++) {
        if(!RG1[i].size()) {
            ans1++;
        }
    }
    for(int i = 1; i <= scc_cnt; i++) {
        if(!G1[i].size()) {
            ans2++;
        }
    }
    if(scc_cnt==1) {  // WA.
        printf("1\n0\n");
        return;
    }
    printf("%d\n", ans1);
    printf("%d\n", max(ans1, ans2));
}

int main()
{
    int x;
    while(scanf("%d", &n)!=EOF) {
        for(int i = 1; i <= n; i++) G[i].clear();
        for(int i = 1; i <= n; i++) {
            for(;;)  {
                scanf("%d", &x);
                if(x!=0) G[i].push_back(x);
                else break;
            }
        }
        find_scc();
        build_DAG();
        work();
    }
    return 0;
}

POJ1236 Network of Schools,古老的榕树,5-wow.com