Stable Members

 1 #include <math.h>
 2 #include <stdio.h>
 3 #include <stdlib.h>
 4 #include <iostream>
 5 #include <algorithm>
 6 #include <string>
 7 #include <string.h>
 8 #include <vector>
 9 #include <map>
10 #include <stack>
11 #include <set>
12 #include <queue>
13 
14 
15 #define LL long long
16 #define INF 0x3f3f3f3f
17 #define ls nod<<1
18 #define rs (nod<<1)+1
19 
20 const int maxn = 2e5 + 10;
21 const int mod = 142857;
22 
23 int col[maxn],un[maxn];
24 std::vector<int> son[maxn],parent[maxn];
25 
26 bool all_same(int now,int color) {
27     int len = parent[now].size();
28     for (int i=0;i<len;i++) {
29         if (col[parent[now][i]] != color)
30             return false;
31     }
32     return true;
33 }
34 
35 
36 
37 void topsort(int x) {
38     if (col[x] != 0)
39         return;
40     col[x] = x;
41     std::queue<int> q;
42     q.push(x);
43     while (!q.empty()) {
44         int now = q.front();
45         q.pop();
46         int len = son[now].size();
47         for (int i=0;i<len;i++) {
48             if (all_same(son[now][i],col[now])) {
49                 col[son[now][i]] = col[now];
50                 q.push(son[now][i]);
51                 un[son[now][i]] = 1;
52             }
53         }
54     }
55 }
56 
57 
58 
59 int main() {
60     int n;
61     scanf("%d",&n);
62     for (int i=1;i<=n;i++) {
63         int k,id;
64         scanf("%d",&k);
65         while (k--) {
66             scanf("%d",&id);
67             parent[i].push_back(id);
68             son[id].push_back(i);
69         }
70     }
71     for (int i=1;i<=n;i++)
72         topsort(i);
73     int ans = 0;
74     for (int i=1;i<=n;i++) {
75         ans += un[i];
76     }
77     printf("%d\n",n-ans);
78     return 0;
79 }