999E - Reachability from the Capital(Codeforces Round #490 (Div. 3))
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.
The first line of input consists of three integers nn, mm and ss (1≤n≤5000,0≤m≤5000,1≤s≤n1≤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 uiui, vivi (1≤ui,vi≤n1≤ui,vi≤n, ui≠viui≠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).
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.
9 9 1
1 2
1 3
2 3
1 5
5 6
6 1
1 8
9 8
7 1
3
5 4 5
1 2
2 3
3 4
4 1
1
The first example is illustrated by the following:
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:
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(n⋅m)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 上一篇: 2011年西北工业大学机试第三题
下一篇: MISC总结——隐写术(三)
推荐阅读
-
【CodeForces】【搜索】999E Reachability from the Capital
-
codeforces 999E Reachability from the Capital targan+缩点
-
CodeForces ~ 999E ~ Reachability from the Capital (思维 + 图的DFS)
-
Codeforces Round #490 (Div. 3) E. Reachability from the Capital(tarjan+连通图)
-
999E - Reachability from the Capital(Codeforces Round #490 (Div. 3))