CF999E Reachability from the Capital dfs graph greedy
There are n 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 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 1 to n.
The following m 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 u to v and from v to u).
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 s, 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:
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:
解法一: 两次 DFS
#include <bits/stdc++.h>
using namespace std;
const int maxn=5050;
int n,m,s;
int cnt;
vector<int>vg[maxn];
vector<int>g[maxn];
bool used[maxn];
bool good[maxn];
int head;
void dfs1(int x){
good[x]=true;
for(int i=0;i<g[x].size();i++){
if(!good[g[x][i]]) dfs1(g[x][i]);
}
}
void dfs2(int x){
used[x]=true;
for(int i=0;i<vg[x].size();i++){
if(!good[vg[x][i]]&&!used[vg[x][i]]) head=vg[x][i],dfs2(vg[x][i]);
}
for(int i=0;i<g[x].size();i++){
if(!good[g[x][i]]) dfs1(g[x][i]);
}
}
int main(){
scanf("%d%d%d",&n,&m,&s);
s--;
for(int i=0;i<m;i++){
int u,v;
scanf("%d%d",&u,&v);
u--;v--;
g[u].push_back(v);
vg[v].push_back(u);
}
dfs1(s);
for(int i=0;i<n;i++){
if(!good[i]){
head=i;
dfs2(i);
cnt++;
dfs1(head);
}
}
printf("%d\n",cnt);
}
方法二,tarjan算法求出除起点所在的强连通分量之外的所有强连通分量,并将其每个缩成一个点,判断这些点还有没有除了该强连通分量之外的边连入(入度为0) 如果为0,则ans++,最后输出ans
#include<bits/stdc++.h>
using namespace std;
const int maxn=5050;
int n,m,s;
int cnt_scc,dfs_clock;
vector<int> g[maxn];
int ind[maxn],vis[maxn],scc[maxn];
int low[maxn],dfn[maxn];
stack<int> st;
void tarjan(int x){
dfn[x]=low[x]=++dfs_clock;
vis[x]=1;
st.push(x);
for(int i=0;i<g[x].size();i++){
int v=g[x][i];
if(!dfn[v])
tarjan(v), low[x]=min(low[x],low[v]);
else if(vis[v])
low[x]=min(low[x],dfn[v]);
}
int t;
if(low[x]==dfn[x]){
do{
t=st.top(); st.pop();
vis[t]=0;
scc[t]=cnt_scc;
}while(x!=t);
cnt_scc++;
}
}
int main(){
scanf("%d%d%d",&n,&m,&s);
s--;
for(int i=0;i<m;i++){
int u,v;
scanf("%d%d",&u,&v);
u--;v--;
g[u].push_back(v);
}
for(int i=0;i<n;i++)
if(!dfn[i]) tarjan(i);
for(int i=0;i<n;i++)
for(int j=0;j<g[i].size();j++){
int v=g[i][j];
if(scc[i]!=scc[v]) ind[scc[v]]++;
}
int ans=0;
for(int i=0;i<cnt_scc;i++)
if(!ind[i]&&i!=scc[s]) ans++;
printf("%d\n",ans);
}