Mr. Kitayuta's Technology CodeForces - 505D（并查集+拓扑排序或dfs找环）题解

2019-11-08 01:33:38

字体：大中小

来源：转载

供稿：网友

题目 Shuseki Kingdom is the world’s leading nation for innovation and technology. There are n cities in the kingdom, numbered from 1 to n.

Thanks to Mr. Kitayuta’s research, it has finally become possible to construct teleportation pipes between two cities. A teleportation pipe will connect two cities unidirectionally, that is, a teleportation pipe from city x to city y cannot be used to travel from city y to city x. The transportation within each city is extremely developed, therefore if a pipe from city x to city y and a pipe from city y to city z are both constructed, people will be able to travel from city x to city z instantly.

Mr. Kitayuta is also involved in national politics. He considers that the transportation between the m pairs of city (ai, bi) (1 ≤ i ≤ m) is important. He is planning to construct teleportation pipes so that for each important pair (ai, bi), it will be possible to travel from city ai to city bi by using one or more teleportation pipes (but not necessarily from city bi to city ai). Find the minimum number of teleportation pipes that need to be constructed. So far, no teleportation pipe has been constructed, and there is no other effective transportation between cities.

Input The first line contains two space-separated integers n and m (2 ≤ n ≤ 105, 1 ≤ m ≤ 105), denoting the number of the cities in Shuseki Kingdom and the number of the important pairs, respectively.

The following m lines describe the important pairs. The i-th of them (1 ≤ i ≤ m) contains two space-separated integers ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi), denoting that it must be possible to travel from city ai to city bi by using one or more teleportation pipes (but not necessarily from city bi to city ai). It is guaranteed that all pairs (ai, bi) are distinct.

Output PRint the minimum required number of teleportation pipes to fulfill Mr. Kitayuta’s purpose.

Example Input 4 5 1 2 1 3 1 4 2 3 2 4 Output 3 Input 4 6 1 2 1 4 2 3 2 4 3 2 3 4 Output 4

题目大意就是城市之间可以修单向的瞬时传送门，现在给出需求（需要那个城市可以到达娜个城市），问你最少需要修多少个传送通道，首先可以知道，对于需求构成的一个联通块，若连通块有环，只需要把连通块里的点修出一个单项环，任意点就可以互相达到了，若无环，只需要修n-1条路就可以满足需求了。所以我们只需要用并查集找出所有的连通块，然后对每个连通块判断环就行，我用了拓扑排序和dfs找环两种方法来做。首先是拓扑排序，拓扑排序本身是针对无环有向图的，通过不断把没有入度的点入队来实现，而若有环，则环上的点始终无法入队，最后处理完它们的入度也不会变成零，这样就很容易找出环了。 dfs找环的方法就是对点赋予状态，0表示没访问过，1表示这个点及其相连的连通块都已经访问过了，-1则表示这个点正在对其dfs深搜访问，若一个点状态为-1又被再一次访问到，那么这肯定就是一个环了。

1.拓扑排序

#include<iostream>#include<string.h>#include<stdio.h>#include<string>#include<vector>#include<algorithm>#include<queue>#include<set>#include<stack>using namespace std;int f[100005];int n, m;vector<int > e[100005];queue<int> que;int F(int x){ if (f[x] == x)return x; return f[x] = F(f[x]); }bool H[100005];int lt[100005];bool vis[100005];int deg[100005];void func(){ while (!que.empty()){ int cnt = que.front(); que.pop(); for (int i = 0; i < e[cnt].size(); i++){ deg[e[cnt][i]]--; if (deg[e[cnt][i]] == 0)que.push(e[cnt][i]); } }}int main(){ int x, y; scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++)f[i] = i; for (int i = 0; i < m; i++){ scanf("%d%d", &x, &y); e[x].push_back(y); deg[y]++; f[F(x)] = F(y); } for (int i = 1; i <= n; i++){ lt[F(i)]++; if (deg[i] == 0)que.push(i); } func(); int ans = 0; for (int i = 1; i <= n; i++){ if (deg[i] != 0)H[F(i)] = 1; } for (int i = 1; i <= n; i++){ if (f[i] == i){ if (H[i])ans += lt[i]; else{ ans += lt[i] - 1; } } } printf("%d", ans); return 0;}

2.DFS找环

#include<iostream>#include<string.h>#include<stdio.h>#include<string>#include<vector>#include<algorithm>#include<queue>#include<set>#include<stack>using namespace std;int f[100005];int n, m;vector<int > e[100005];queue<int> que;int F(int x){ if (f[x] == x)return x; return f[x] = F(f[x]); }bool H[100005];int lt[100005];bool vis[100005];int c[100005];void dfs(int cnt){ c[cnt] = -1; for (int i = 0; i < e[cnt].size(); i++){ int cur = e[cnt][i]; if (c[cur] == -1){ H[F(cur)] = 1; break; } else if (c[cur] == 0){ dfs(cur); } } c[cnt] = 1;}int main(){ int x, y; scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++)f[i] = i; for (int i = 0; i < m; i++){ scanf("%d%d", &x, &y); e[x].push_back(y); //deg[y]++; f[F(x)] = F(y); } for (int i = 1; i <= n; i++){ lt[F(i)]++; if (c[i] == 0)dfs(i); //if (deg[i] == 0)que.push(i); }// func(); int ans = 0; for (int i = 1; i <= n; i++){ if (f[i] == i){ if (H[i])ans += lt[i]; else{ ans += lt[i] - 1; } } } printf("%d", ans); return 0;}

上一篇：leecode 解题总结：165. Compare Version Numbers

下一篇：[BZOJ1567][JSOI2008]Blue Mary的战役地图（二分+hash）