main.cpp

ACM题解：The Bottom of a Graph 求图的强连通分量的好例子

#include <iostream>
#include <vector>

using namespace std;

typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<vi> vvi;

void dfs(vvi &vvs, vb &used, vi &finish, int v) {

    vi vv = vvs[v];
    used[v] = true;
    for(int i=0; i<vv.size(); i++) {
        if(!used[vv[i]]) {
            dfs(vvs, used, finish, vv[i]);
        }
    }
    //cout<<v<<endl;
    finish.push_back(v);
}

void rdfs(vvi &vvs, vb &used, vi &finish, int v) {
    //cout<<"JJ: "<<v<<endl;
    vi vv = vvs[v];
    used[v] = true;
    for(int i=0; i<vv.size(); i++) {
        if(!used[vv[i]]) {
            finish[vv[i]] = finish[v];
            rdfs(vvs, used, finish, vv[i]);
        }
    }
}

int main(){
    int vn, en;
    int i, j;
    int v1, v2;
    bool sink;
    //freopen("bottom.in.txt","r",stdin);
    //freopen("bottom.out.txt","r",stdout);
    cin>>vn;
    while(vn != 0) {
        vvi vvs(vn+1, vi(0));
        vvi rvvs(vn+1, vi(0));
        cin>>en;
        for(i=0; i<en; i++) {
            cin>>v1>>v2;
            vvs[v1-1].push_back(v2-1);
            rvvs[v2-1].push_back(v1-1);
        }
        vb used(vn, false);
        vi finish(0);
        for(i=0; i<vn; i++) {
            if(!used[i]) {
                dfs(vvs, used, finish, i);
            }
        }

        vb rused(vn, false);
        vi rfinish(vn);
        int v;
        for(i=vn-1; i>=0; i--) {
            v = finish[i];
            if(!rused[v]) {
                rfinish[v] = v;
                rdfs(rvvs, rused, rfinish, v);
            }
        }/*
        for(i=0;i<vn;i++) {
            cout<<rfinish[i]<<" ";
        }*/
        vb sink(vn, true);
        for(i=0; i<vn; i++) {
            vi vv = vvs[i];
            for(j=0;j<vv.size();j++) {
                if(rfinish[i] != rfinish[vv[j]]) {
                    sink[rfinish[i]] = false;
                }
            }
        }
        for(i=0; i<vn; i++) {
            if(sink[rfinish[i]]) {
                cout<<i+1<<" ";
            }
        }
        cout << endl;
        cin>>vn;
    }
}