Forwarding Emails

#include<bits/stdc++.h>

using namespace std;

int dp[50005];

vector<int>graph[50005];

bool color[50005],cycle;

int node;

int dfs(int u)
{
    int len = graph[u].size(),i;

    if(dp[u]!=-1)
        return dp[u];

    color[u] = true;

    dp[u] = 1;

    for(i=0; i<len; i++)
    {
        if(!color[graph[u][i]])
        {
            dp[u]+=dfs(graph[u][i]);
        }
        else
        {
            cycle = true;

            node = graph[u][i];
        }
    }

    color[u] = false;

    return dp[u];
}

void again_dfs(int u)
{
    int len = graph[u].size(),i;

    color[u] = true;

    dp[u] = dp[node];

    for(i=0; i<len; i++)
    {
        if(!color[graph[u][i]])
        {
            again_dfs(graph[u][i]);
        }
    }

    color[u] = false;
}

int main()
{
    int tc,n,test,i,u,v,martian,mx;

    scanf("%d",&test);

    for(tc=1; tc<=test; tc++)
    {
        scanf("%d",&n);

        for(i=1; i<=n; i++)
        {
            scanf("%d%d",&u,&v);

            graph[u].push_back(v);
        }

        memset(dp,-1,sizeof dp);

        mx = -1;

        for(i=1; i<=n; i++)
        {
            cycle = false;

            dfs(i);

            if(cycle)
            {
                again_dfs(node);
            }

            if(mx<dp[i])
            {
                mx = dp[i];

                martian = i;
            }
        }

        printf("Case %d: %d\n",tc,martian);

        for(i=1; i<=n; i++)
        {
            graph[i].clear();
        }
    }

    return 0;
}