-
Notifications
You must be signed in to change notification settings - Fork 1
Open
Labels
Description
https://lightoj.com/problem/forwarding-emails
Test case is missing which could give TLE for the tutorial solution.
#include<bits/stdc++.h>
using namespace std;
int vis[50005],dist[50005],adjacent[50005],cnt=0;
int dfs(int uu)
{
vis[uu]=1;
int vv=adjacent[uu];
if(!vis[vv])
{
cnt++;
dfs(vv);
}
vis[uu]=0;
return dist[uu]=cnt;
}
main()
{
int ts,cs=1;
scanf("%d",&ts);
while(ts--)
{
int n,u,v,mx=0,ans=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&u,&v);
adjacent[u]=v;
}
memset(vis,0,sizeof(vis));
memset(dist,-1,sizeof(dist));
for(int i=1;i<=n; i++)
{
cnt=1;
if(dist[i]==-1)
{
dfs(i);
dist[i]=cnt;
}
if(cnt>mx)
{
mx=cnt;
ans=i;
}
}
printf("Case %d: %d\n",cs++,ans);
}
}Test case :
1
50000
1 2
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
...
...
49998 49997
49999 49998
50000 49999I also can make number of test cases 20 and repeat the same graph 20 times.