Solution for POJ 2186 - Popular Cows

My first blog in English!

Solution #

I learnt Tarjan’s algorithm in this video. Very good visualization.

First we find all the strongly conncted components in the given relationship graph. All the vetices in the same component can be treated as one point in the graph so we could get a DAG. The cows which is considered popular by all other cows are cows in the SCC with 0 out-degree. If there are more than one SCCs with 0 out-degree the answer is 0, otherwise the anser the number of cows in that SCC.

Some details in the implementation:

I used the $low$ value as the id of each vetices so all the vertices in the same SCC can be seen as one point.
$low$ values are now consecutive so when you encounter one $low$ value with 0 out-degree, you have to change its out-degree to a none-zero value in case you count it again.

Code #

#include<iostream>
#include<vector>
#include<cstring>
 
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define fore(i, l, r) for (int i = (int)(l); i <= (int)(r); ++i)
#define ford(i, n) for (int i = (int)(n)-1; i >= 0; --i)
#define pb push_back
#define ms(a, x) memset(a, x, sizeof(a))
 
#define endl '\n'
using namespace std;
 
const int INF = 0x3f3f3f3f;
typedef long long ll;
typedef pair<int, int> pii;
 
int n,m;
const int N=1e4+5;
vector<int> vec[N];
int id=1;
int ids[N],low[N];
bool onstack[N];
int stk[N],top=-1;
int out[N];
void dfs(int x){
    stk[++top]=x;
    onstack[x]=1;
    ids[x]=low[x]=id++;
    forn(i,vec[x].size()){
        int to=vec[x][i];
        if(ids[to]==-1) dfs(to);
        if(onstack[to]) low[x]=min(low[to],low[x]);
    }
    if(ids[x]==low[x]){
        while(top>-1){
            int node=stk[top--];
            onstack[node]=0;
            low[node]=ids[x];
            if(node==x) break;
        }
    }
}
void tarjan(){
    for1(i,n) ids[i]=-1;
    for1(i,n){
        if(ids[i]==-1) dfs(i);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    forn(i,m){
        int u,v;
        cin>>u>>v;
        vec[u].pb(v);
    }
    tarjan();
    for1(i,n){
        forn(j,vec[i].size()){
            int it=vec[i][j];
            if(low[it]!=low[i])
            out[low[i]]++;
        }
    }
    int cnt=0;
    int p;
    for1(i,n) if(out[low[i]]==0) {
        out[low[i]]=1;
        cnt++;
        p=low[i];
    }
    if(cnt==1){
        int ans=0;
        for1(i,n) if(low[i]==p) ans++;
        cout<<ans;
    }else cout<<0;
    
    return 0;
}