1 /*
2 题意：第i个人选择第a[i]个人，问组成强联通分量(自己连自己也算)外还有多少零散的人
3 有向图强联通分量-Tarjan算法：在模板上加一个num数组，记录每个连通分量的点数，若超过1，则将连通点数相加
4 用总点数-ans则是零散的点
5 详细解释：http://www.bubuko.com/infodetail-927304.html
6 */
7 #include <cstdio>
8 #include <cstring>
9 #include <algorithm>
10 #include <vector>
11 #include <stack>
12 using namespace std;
13
14 const int MAXN = 1e5 + 10;
15 const int INF = 0x3f3f3f3f;
16 vector<int> G[MAXN];
17 stack<int> S;
18 int pre[MAXN], low[MAXN];
19 int instack[MAXN], num[MAXN];
20 int dfs_clock, scc_cnt;
21 int n, ans;
22
23 void DFS(int u)
24 {
25 instack[u] = 1;
26 pre[u] = low[u] = ++dfs_clock;
27 S.push (u);
28 for (int i=0; i<G[u].size (); ++i)
29 {
30 int v = G[u][i];
31 if (!pre[v])
32 {
33 DFS (v); low[u] = min (low[u], low[v]);
34 }
35 else if (instack[v] == 1)
36 {
37 low[u] = min (low[u], pre[v]);
38 }
39 }
40
41 if (low[u] == pre[u])
42 {
43 scc_cnt++;
44 for (; ; )
45 {
46 int x = S.top (); S.pop ();
47 instack[x] = 0;
48 num[scc_cnt]++;
49 if (x == u) break;
50 }
51 }
52 }
53
54 void Tarjan(void)
55 {
56 dfs_clock = scc_cnt = 0;
57 memset (pre, 0, sizeof (pre));
58 memset (low, 0, sizeof (low));
59 memset (num, 0, sizeof (num));
60 memset (instack, 0, sizeof (instack));
61 while (!S.empty ()) S.pop ();
62
63 for (int i=1; i<=n; ++i)
64 {
65 if (!pre[i]) DFS (i);
66 }
67 }
68
69 int main(void) //UVALive 6511 Term Project
70 {
71 freopen ("L.in", "r", stdin);
72
73 int t; scanf ("%d", &t);
74 while (t--)
75 {
76 ans = 0; scanf ("%d", &n);
77 for (int i=1; i<=n; ++i) G[i].clear ();
78 for (int i=1; i<=n; ++i)
79 {
80 int x; scanf ("%d", &x);
81 G[i].push_back (x);
82 if (i == x) ans++;
83 }
84
85 Tarjan ();
86 for (int i=1; i<=scc_cnt; ++i)
87 {
88 if (num[i] > 1) ans += num[i];
89 }
90 printf ("%d
", n - ans);
91 }
92
93 return 0;
94 }
Tarjan UVALive 6511 Term Project
编译人生，运行世界！