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

CF999E Reachability from the Capital dfs graph greedy

程序员文章站 2022-05-15 14:02:16
...

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:

CF999E Reachability from the Capital dfs graph greedy

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:

CF999E Reachability from the Capital dfs graph greedy

 

 

解法一: 两次 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);
}