popular cows(强连通分量gabow).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
#define NMAX 11000 

vector< vector< int > > path;
int n,m, scc, step;
int order[NMAX], order_pos, id[NMAX], id_total[NMAX];
int order2[NMAX], order2_pos;
int vis[NMAX];
int out_degre[NMAX];

void dfs(int pos)
{
    int i,j,next,l,pre;

    vis[pos] = step ++;
    order[ order_pos ++ ] = pos;
    order2[ order2_pos ++ ] = pos;
    l = path[pos].size();
    for (i=0;i<l;i++) {
        next = path[pos][i];
        if (vis[next] == 0) {
            dfs(next);
        }
        else if (id[next] == 0) {//have a circle and belong to nothing
            while (vis[ order2[order2_pos -1] ] > vis[next]) {//back to begin of circle
                order2_pos --;
            }
        }
    }//for i
    if (order2[order2_pos -1] == pos) {//if pos back to begin of scc
        order2_pos --;
    }
    else {
        return ;
    }
    do {//record scc
        pre = order[order_pos -1];
        id[pre] = scc;
        order_pos --;
    } while(pre != pos);
    scc ++;
}

void Gabow()
{
    int i,j,l;
    //dfs in original graph
    memset(id, 0, sizeof(id));
    memset(vis, 0, sizeof(vis));
    scc = 1;
	step = 1;
    order_pos = order2_pos = 0;
    for (i=1; i<=n ;i++) {
        if (vis[i] == 0) {
            dfs(i);
        }
    }
    
    //statist
    scc --;
    memset(id_total, 0, sizeof(id_total));
    for (i=1;i<=n;i++) {
        id_total[ id[i] ] ++;
    }
    
    memset(out_degre, 0, sizeof(out_degre));
    for (i=1;i<=n;i++) {
        l = path[i].size();
        int id1 = id[i];
        for (j=0;j<l;j++) {
            int id2 = id[ path[i][j] ];
            if (id1 != id2) {//id1 -> id2
                out_degre[id1] ++;
            }
        }
    }
    int ans_id,zero_degre = 0;
    for (i=1;i<=scc;i++) {
        if (out_degre[i] == 0) {
            zero_degre ++;
            ans_id = i;
        }
    }

    if (zero_degre > 1) {
        printf("0\n");
    }
    else {
        printf("%d\n",id_total[ ans_id ]);
    }
}

int main()
{
    int i,j;
    while (scanf("%d %d",&n,&m)==2) {
        path.resize(n+10);
        for (i=0;i<=n;i++) {
            path[i].clear();
        }
        order_pos = 0;
        //set graph
        for (i=0;i<m;i++) {
            int x,y;
            scanf("%d %d",&x,&y);
            path[x].push_back(y);
        }
        Gabow();
    }
}