[UVA] 12442 - Forwarding Emails

#include<bits/stdc++.h>
using namespace std;
#define N 50005
int to[N],pre[N],sccno[N],cnt[N],val[N],dfs_cnt,scc_cnt;
vector<int> sta,G[N];
int dfs(int u){
    int lowu=pre[u]=++dfs_cnt;
    sta.push_back(u);
    /**************/
    int v=to[u];
    if(pre[v]==0){
        int lowv=dfs(v);
        lowu=min(lowu,lowv);
    }
    else if(!sccno[v]){
        lowu=min(lowu,pre[v]);
    }
    /**************/
    if(lowu==pre[u]){
        scc_cnt++;
        while(sta.size()){
            int x=sta.back();
            sta.pop_back();
            sccno[x]=scc_cnt;
            cnt[scc_cnt]++;
            if(x==u) break;
        }
    }
    return lowu;
}
int dfs2(int u){
    if(val[u]) return val[u];
    int i,sum=cnt[u];
    for(i=0;i<G[u].size();i++){
        int v=G[u][i];
        sum+=dfs2(v);
    }
    return val[u]=sum;
}
int main(){
    int t,n,m,x,y,i,j,C=0;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        memset(pre,0,sizeof(pre));
        memset(sccno,0,sizeof(sccno));
        memset(cnt,0,sizeof(cnt));
        memset(val,0,sizeof(val));
        for(i=0;i<n;i++){
            scanf("%d%d",&x,&y);
            to[x]=y;
        }
        scc_cnt=dfs_cnt=0;
        for(i=1;i<=n;i++){
            if(pre[i]==0){
                sta.clear();
                dfs(i);
            }
        }
        for(i=1;i<=scc_cnt;i++){
            G[i].clear();
        }
        for(i=1;i<=n;i++){
            x=i,y=to[i];
            if(sccno[x]!=sccno[y]){
                G[sccno[x]].push_back(sccno[y]);
            }
        }
        for(i=1;i<=scc_cnt;i++){
            dfs2(i);
        }
        int ans=0,id;
        for(i=1;i<=n;i++){
            if(val[sccno[i]]>ans){
                ans=val[sccno[i]],id=i;
            }
        }
        printf("Case %d: %d\n",++C,id);
    }
}