解题笔记——NIT 遥远的村庄

某个小镇有 N 个村庄，村庄编号1-N，给出 M 条单向道路，不存在环，即不存在村庄A可以到达村庄B 且村庄B也可以到达村庄A的情况。
如果村庄A与村庄B之间存在一条单向道路，则说村庄A和村庄B之间存在联系，联系具有无向性，即如果村庄A和村庄B有联系，则村庄B和村庄A有联系；联系具有传递性，即如果存在村庄A和村庄B有联系，村庄B和村庄C有联系，则村庄A和村庄C有联系。
现在小镇要在某些村庄里建垃圾站，对建垃圾站的村庄要满足与之有联系的村庄都可以通过单向道路到达该村庄。问小镇能建多少个垃圾站。

Input

输入包含多组数据，对于每组数据：
第一行输入N，M，数据范围1<=n<=1000,0<=m<10000。
接下来M行，每行两个整数，s，t，代表 s 可以到达 t 。

Output

对于每组数据，输出一个整数代表答案。

Sample Input

Sample Output

Hint

案例中有10个村庄，道路情况如下：

1->2->3->4

6->7->8

9->10

村庄4可以建垃圾站，因为与之有联系的村庄都能到达他；同理村庄5，村庄8，村庄10，所以答案有4个。

解题思路：

要建垃圾站的话，该村庄所在的关于村庄联系的联通块内的结点数和他的单向道路能到达的结点数相同，但是建边要反向建，本来u到v的边要建成v到u的边，用并查集算各个联通块内结点数，然后dfs算能到达多少个结点再跟该联通块内结点总数比较，相等的话说明可以建垃圾站

难点在看不懂题意

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 typedef unsigned long long ull;
 5 #define INF 0x3f3f3f3f
 6 const ll MAXN = 1e3 + 7;
 7 const ll MAXM = 1e4 + 7;
 8 const ll MOD = 1e9 + 7;
 9 const double pi = acos(-1);
10 int n, m;
11 int vis[MAXN];
12 int pre[MAXN];
13 vector<int> V[MAXN];
14 int root[MAXN]; //根结点的位置记录联通块内结点数
15 int cnt;
16 void init()
17 {
18     memset(vis, 0, sizeof(vis));
19     memset(root, 0, sizeof(root));
20     for (int i = 1; i <= n; i++)
21         pre[i] = i, V[i].clear();
22 }
23 int find(int x) //查找根结点
24 {
25     int r = x;
26     while (r != pre[r]) //寻找根结点
27         r = pre[r];
28     int i = x, j;
29     while (pre[i] != r) //路径压缩
30     {
31         j = pre[i];
32         pre[i] = r;
33         i = j;
34     }
35     return r;
36 } //并查集求联通块块数
37 //遍历有向图结点
38 void DFS(int u)
39 {
40     cnt++;
41     vis[u] = 1;
42     for (int i = 0; i < V[u].size(); i++)
43     {
44         int v = V[u][i];
45         if (!vis[v])
46         { //如果该节点未被访问，则深度遍历
47             DFS(v);
48         }
49     }
50 }
51 int main()
52 {
53     while (~scanf("%d%d", &n, &m))
54     {
55         init();
56         int ans = 0;
57         for (int i = 0; i < m; i++)
58         {
59             int u, v;
60             scanf("%d%d", &u, &v);
61             V[v].push_back(u);
62             int fa = find(u);
63             int fb = find(v);
64             if (fa != fb)
65                 pre[fa] = fb;
66         }
67         for (int i = 1; i <= n; i++)
68             root[find(i)]++;
69         for (int i = 1; i <= n; i++)
70         {
71             memset(vis, 0, sizeof(vis));
72             cnt = 0;
73             DFS(i);
74             if (cnt == root[find(i)])
75                 ans++;
76         }
77         printf("%d
", ans);
78     }
79     return 0;
80 }
81 /* 14 7
82 1 8
83 2 8
84 4 5
85 7 8
86 9 7
87 6 7
88  6 8
89 */