UVA 12442 Forwarding Emails Solution

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
#define INF (1<<30)
#define eps (1e-7)
const int N=50005;
vector<int >adj[N];
int number[N];
int dp[N];
int low[N],dfn[N],sta[N],id[N],top,idx,scnt;
bool insta[N],vis[N];
void init(int n)
{
    top=0;idx=0;scnt=0;
    memset(dp,-1,sizeof(dp));
    memset(vis,0,sizeof(vis));
    memset(insta,0,sizeof(insta));
    memset(low,0,sizeof(low));
    memset(dfn,0,sizeof(dfn));
    memset(number,0,sizeof(number));
    for(int i=0;i<=n;i++) adj[i].clear();
}
void tarjan(int u)
{
    insta[u]=1; sta[top++]=u;
    low[u]=dfn[u]=++idx;
    for(int i=0;i<(int)adj[u].size();i++) {
        int v=adj[u][i];//用vector存的点
        if(!dfn[v]) {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(insta[v]&&dfn[v]<low[u]) low[u]=dfn[v];
    }
    //cout<<"u="<<u<<endl;
    //cout<<"low"<<low[u]<<" "<<dfn[u]<<endl;
    if(low[u]==dfn[u]) {
        int tmp;
        ++scnt;
        do {
            tmp=sta[--top];
            insta[tmp]=0;
            id[tmp]=scnt;
            number[scnt]++;
        }while(tmp!=u);
    }
}
int dfs(int ind)
{
    int &res=dp[id[ind]];
    if(res!=-1) return res;

    res=0;
    for(int i=0;i<(int)adj[ind].size();i++)
    {
        int v=adj[ind][i];
        if(id[v]!=id[ind]) res=max(res,dfs(v)+number[id[v]]);
    }
    return res;
}
int main()
{
    int t,t_cnt=0;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        init(n+5);
        for(int i=0;i<n;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            adj[a].push_back(b);
        }
        for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
        int res=0,ind=0;
        //for(int i=1;i<=n;i++) printf("%d ",id[i]);puts("");
        for(int i=1;i<=n;i++)
        {
            int tmp=dfs(i)+number[id[i]];
            //cout<<tmp<<endl;
            if(res<tmp)
            {
                res=tmp;
                ind=i;
            }
        }
        printf("Case %d: %d\n",++t_cnt,ind);
    }
 return 0;
}