SHOW:
|
|
- or go back to the newest paste.
1 | #include <iostream> | |
2 | #include <cstring> | |
3 | #include <string> | |
4 | #include <algorithm> | |
5 | #include <map> | |
6 | #include <vector> | |
7 | #include <set> | |
8 | #include <queue> | |
9 | #include <cstdlib> | |
10 | #include <cstdio> | |
11 | using namespace std; | |
12 | const int maxn = 507; | |
13 | ||
14 | vector<string> S; | |
15 | map<string, int> idx; | |
16 | ||
17 | vector<int> g[maxn]; | |
18 | bool used[maxn]; | |
19 | - | int d[maxn], p[maxn]; |
19 | + | int d[maxn]; |
20 | int bfs(int st) | |
21 | { | |
22 | memset(used, 0, sizeof(used)); | |
23 | memset(d, 0, sizeof(d)); | |
24 | - | memset(p, -1, sizeof(p)); |
24 | + | |
25 | Q.push(st); | |
26 | d[st] = 0; | |
27 | used[st] = true; | |
28 | while (!Q.empty()) | |
29 | { | |
30 | int v = Q.front(); | |
31 | Q.pop(); | |
32 | ||
33 | for (int i = 0; i < g[v].size(); ++i) | |
34 | { | |
35 | int to = g[v][i]; | |
36 | if (!used[to]) | |
37 | { | |
38 | Q.push(to); | |
39 | d[to] = d[v] + 1; | |
40 | used[to] = true; | |
41 | - | p[to] = v; |
41 | + | |
42 | else | |
43 | { | |
44 | - | else if (to != p[v]) |
44 | + | |
45 | } | |
46 | } | |
47 | } | |
48 | return 0; | |
49 | } | |
50 | ||
51 | int main() | |
52 | { | |
53 | //freopen("input.txt", "r", stdin); | |
54 | int n; | |
55 | cin >> n; | |
56 | vector<pair<string, string> > Q; | |
57 | for (int i = 0; i < n; ++i) | |
58 | { | |
59 | string a, b; | |
60 | cin >> a >> b; | |
61 | Q.push_back(make_pair(a, b)); | |
62 | S.push_back(a); | |
63 | S.push_back(b); | |
64 | } | |
65 | sort(S.begin(), S.end()); | |
66 | S.resize(distance(S.begin(), unique(S.begin(), S.end()))); | |
67 | ||
68 | for (int i = 0; i < (int)S.size(); ++i) | |
69 | { | |
70 | idx[S[i]] = i; | |
71 | } | |
72 | ||
73 | for (int i = 0; i < n; ++i) | |
74 | { | |
75 | int a = idx[Q[i].first], | |
76 | b = idx[Q[i].second]; | |
77 | g[a].push_back(b); | |
78 | } | |
79 | ||
80 | - | g[b].push_back(a); |
80 | + | |
81 | for (int i = 0; i < (int)S.size(); ++i) | |
82 | { | |
83 | ans = max(ans, bfs(i)); | |
84 | } | |
85 | if (ans < 3) | |
86 | { | |
87 | cout << 0; | |
88 | } | |
89 | else | |
90 | { | |
91 | cout << ans; | |
92 | } | |
93 | ||
94 | return 0; | |
95 | } |