“... so forward this to ten other people, to prove that you believe the emperor has new clothes.”
Aren’t those sorts of emails annoying?
Martians get those sorts of emails too, but they have an innovative way of dealing with them.
Instead of just forwarding them willy-nilly, or not at all, they each pick one other person they know
to email those things to every time - exactly one, no less, no more (and never themselves). Now, the
Martian clan chieftain wants to get an email to start going around, but he stubbornly only wants to
send one email. Being the chieftain, he managed to find out who forwards emails to whom, and he
wants to know: which Martian should he send it to maximize the number of Martians that see it?
Input
The first line of input will contain T (≤ 20) denoting the number of cases.
Each case starts with a line containing an integer N (2 ≤ N ≤ 50000) denoting the number of
Martians in the community. Each of the next N lines contains two integers: u v (1 ≤ u, v ≤ N , u ? = v)
meaning that Martian u forwards email to Martian v.
Output
For each case, print the case number and an integer m, where m is the Martian that the chieftain
should send the initial email to. If there is more than one correct answer, output the smallest number.
Sample Input
Sample Output
3
3
1
2
3
4
1
2
4
3
5
1
2
5
3
4
2
3
1
2
1
3
2
2
1
3
4
5
Sample Output
Case 1: 1
Case 2: 4
Case 3: 3
?
題意是說發短信,每個人只會給一個人發,問從哪個人開始發,能傳到的人最多
思路是每個人開始做一遍dfs...
毫無意外的TLE了
一個容易想到的剪枝是,如果在第i次之前的路徑上的點,在之后以它作為起點遍歷一定不優.
我們可以用一個數組vis標記上(注意不要和為了dfs的標記數組vis2混淆,vis2標記的主要作用是判斷是否成環)
?
sad,看來還是要提高自己的搜索姿勢啊....
/*************************************************************************> File Name: code/2015summer/sea#2/B.cpp> Author: 111qqz> Email: rkz2013@126.com > Created Time: 2015年07月28日 星期二 14時59分16秒************************************************************************/#include<iostream> #include<iomanip> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<string> #include<map> #include<set> #include<queue> #include<vector> #include<stack> #define y0 abc111qqz #define y1 hust111qqz #define yn hez111qqz #define j1 cute111qqz #define tm crazy111qqz #define lr dying111qqz using namespace std; #define REP(i, n) for (int i=0;i<int(n);++i) typedef long long LL; typedef unsigned long long ULL; const int N=5E4+7; int a[N]; bool vis[N],vis2[N]; int u,v,n; int dfs(int x) {int res=0;vis2[x]=true;int tmp = a[x];if (!vis2[tmp]){res = dfs(tmp)+1; //當前這個認能傳的長度=他傳的人能傳的長度+1 }vis[x] = true;vis2[x] = false;return res;} int main() {int T;cin>>T;int cas = 0;while (T--){memset(vis,false,sizeof(vis));cas++;scanf("%d",&n);for ( int i = 0 ; i < n; i++ ){scanf("%d %d",&u,&v);a[u]=v;}int mx = - 1;int ans;for ( int i = 1 ; i <= n ; i++){// memset(vis2,false,sizeof(vis2));if (vis[i]) continue; //如果在上一次的dfs中經過了i,那么從i開始傳播一定是之前標記i的那次開始傳播的子鏈,一定不優.int tmp = dfs(i); // cout<<dfs(i,1)<<endl;if (tmp>mx){mx = tmp;ans = i;}}printf("Case %d: %d\n",cas,ans);}return 0; }
?
