UVa 12442 Forwarding Emails

 1  #include <stdio.h>

 2  #include <stdlib.h>

 3  #include <iostream>

 4  #include <algorithm>

 5  #include <vector>

 6  using namespace std;

 7  vector<int> edges,sum;

 8  vector<bool> vis;

 9  int dfs(int s)

10  {

11      if(vis[s]) return 0;

12      vis[s]=true;

13      int tot=1;

14      if(edges[s]!=-1 &&vis[edges[s]]==false)

15      {

16          tot=(1+dfs(edges[s]));

17          vis[edges[s]]=false;

18      }

19      return sum[s]=tot;

20  }

21  int main()

22  {

23      int cas;

24      cin>>cas;

25      for(int cc=1; cc<=cas; cc++)

26      {

27          int n;

28          cin>>n;

29          edges.assign(n+5,-1);

30          vis.assign(n+5,false);

31          sum.assign(n+5,-1);

32          for(int i=0; i<n; i++)

33          {

34              int a,b;

35              cin>>a>>b;

36              edges[a]=b;

37          }

38          int maxn=0,ans=0,tmp;

39          for(int i=1; i<=n; i++)

40          {

41              tmp=0;

42              vis[i-1]=false;

43              if(sum[i]==-1) tmp=dfs(i);

44              if(tmp>maxn)

45              {

46                  ans=i;

47                  maxn=tmp;

48              }

49          }

50          printf("Case %d: %d\n",cc,ans);

51      }

52      return 0;

53  }