欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

999E - Reachability from the Capital(Codeforces Round #490 (Div. 3))

程序员文章站 2022-05-15 14:06:10
...

                                                                                here is the problem

E. Reachability from the Capital
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are nn cities and mm roads in Berland. Each road connects a pair of cities. The roads in Berland are one-way.

What is the minimum number of new roads that need to be built to make all the cities reachable from the capital?

New roads will also be one-way.

Input

The first line of input consists of three integers nnmm and ss (1n5000,0m5000,1sn1≤n≤5000,0≤m≤5000,1≤s≤n) — the number of cities, the number of roads and the index of the capital. Cities are indexed from 11 to nn.

The following mm lines contain roads: road ii is given as a pair of cities uiuivivi (1ui,vin1≤ui,vi≤nuiviui≠vi). For each pair of cities (u,v)(u,v), there can be at most one road from uu to vv. Roads in opposite directions between a pair of cities are allowed (i.e. from uu to vv and from vv to uu).

Output

Print one integer — the minimum number of extra roads needed to make all the cities reachable from city ss. If all the cities are already reachable from ss, print 0.

Examples
input
Copy
9 9 1
1 2
1 3
2 3
1 5
5 6
6 1
1 8
9 8
7 1
output
Copy
3
input
Copy
5 4 5
1 2
2 3
3 4
4 1
output
Copy
1
Note

The first example is illustrated by the following:

999E - Reachability from the Capital(Codeforces Round #490 (Div. 3))

For example, you can add roads (6,46,4), (7,97,9), (1,71,7) to make all the cities reachable from s=1s=1.

The second example is illustrated by the following:

999E - Reachability from the Capital(Codeforces Round #490 (Div. 3))

In this example, you can add any one of the roads (5,15,1), (5,25,2), (5,35,3), (5,45,4) to make all the cities reachable from s=5s=5.


solution:

This problem is (almost) equivalent to the following: count the number of sources (the vertices with indegree equal to 00) in the given graph's condensation. Thus, there exist solutions with complexity O(n+m)O(n+m). However, the constraints in the problem are small, so solutions with complexity O(nm)O(n⋅m) also pass.

One of these solutions is the following: first, let's mark all the vertices reachable from ss as good, using a simple DFS. Then, for each bad vertex vv, count the number of bad vertices reachable from vv (it also can be done by simple DFS). Let this number be cntvcntv. Now, iterate over all bad vertices in non-increasing order of cntvcntv. For the current bad vertex vv, if it is still not marked as good, run a DFS from it, marking all the reachable vertices as good, and increase the answer by 11 (in fact, we are implicitly adding the edge (s,v)(s,v)). It can be proved that this solution gives an optimal answer.


(copy from here


算了,不秀英语了,下面进入正题。

这一题的思路其实也不难(但比赛写了个缩点被卡shi)

这题就是dfs,只不过要用敏锐目光察觉出来


上代码:  其实也不难理解,看看代码就懂了

#include <bits/stdc++.h>

using namespace std;

const int N = 5010;

int n, m, s;
vector<int> g[N];
bool used[N];
bool ok[N];

int cnt;

void dfs1(int v) {
	ok[v] = true;
	for (auto to : g[v])
		if (!ok[to])
			dfs1(to);
}

void dfs2(int v) {
	used[v] = true;
	++cnt;
	for (auto to : g[v])
		if (!used[to] && !ok[to])
			dfs2(to);
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n >> m >> s;
	--s;
	for (int i = 0; i < m; ++i) {
		int x, y;
		cin >> x >> y;
		--x, --y;
		g[x].push_back(y);
	}
	
	dfs1(s);
	
	vector<pair<int, int>> val;
	for (int i = 0; i < n; ++i) {
		if (!ok[i]) {
			cnt = 0;
			memset(used, false, sizeof(used));
			dfs2(i);
			val.push_back(make_pair(cnt, i));
		}
	}
	sort(val.begin(), val.end());
	reverse(val.begin(), val.end());
	
	int ans = 0;
	for (auto it : val) {
		if (!ok[it.second]) {
			++ans;
			dfs1(it.second);
		}
	}
	
	cout << ans << endl;
	
	return 0;
}
详情请进入codeforces