Timus 1742. Team building
1 /*
2 * File: Timus 1742. Team building
3 * Author: xiaotian @ hnu
4 * Created on 2010年10月4日, 下午2:54
5 * 题解：
6 */
7 #include <iostream>
8 #include <string>
9 #include <set>
10 #include <map>
11 #include <vector>
12 #include <algorithm>
13 using namespace std;
14 const int N = 100008;
15
16 int deg[N];
17 int nxt[N];
18 int vised[N], cnt, beg;
19
20 int dfs(int a) {
21 if (vised[a])
22 if (vised[a] >= beg) return vised[a] + 1 - beg;
23 else return cnt - beg;
24 vised[a] = cnt++;
25 return dfs(nxt[a]);
26 }
27
28 int main() {
29 int n;
30 while (scanf("%d", &n) != EOF) {
31 cnt = 1;
32 memset(deg, 0, sizeof (deg));
33 for (int i = 0; i < n; i++) {
34 scanf("%d", nxt + i);
35 nxt[i]--;
36 deg[nxt[i]]++;
37 }
38 int maxR = 0, minR = 0;
39 for (int i = 0; i < n; i++, cnt++)
40 if (!deg[i]) {
41 beg = cnt;
42 minR++;
43 maxR += dfs(i);
44 }
45 for (int i = 0; i < n; i++)
46 if (!vised[i]) {
47 minR++, maxR++;
48 int p = i;
49 while (!vised[p]) {
50 vised[p] = 1;
51 p = nxt[p];
52 }
53 }
54 printf("%d %d\n",minR,maxR);
55 break;
56 }
57 return 0;
58 }