-
Notifications
You must be signed in to change notification settings - Fork 0
/
12442.cpp
62 lines (51 loc) · 826 Bytes
/
12442.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;
vector<int> g;
vector<int> visited;
vector<int> path_len;
int n;
int dfs(int u)
{
visited[u] = true;
int v = g[u];
int length(0);
if (!visited[v])
length = 1 + dfs(v);
visited[u] = false;
return path_len[u] = length;
}
int main()
{
ios_base::sync_with_stdio(false);
int t, test(1);
cin >> t;
while (t--)
{
cin >> n;
g.assign(n, 0);
visited.assign(n, false);
path_len.assign(n, -1);
for (int i = 0; i < n; i++)
{
int u, v;
cin >> u >> v;
g[u - 1] = v - 1;
}
int max_len = -1;
int pos = 0;
for (int i = 0; i < n; i++)
{
if (path_len[i] == -1)
{
dfs(i);
if (path_len[i] > max_len)
{
max_len = path_len[i];
pos = i;
}
}
}
cout << "Case " << test++ << ": " << ++pos << endl;
}
return 0;
}