codeforces 999E Reachability from the Capital targan+缩点
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 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 ).
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
9 9 1 1 2 1 3 2 3 1 5 5 6 6 1 1 8 9 8 7 1
Output
3
Input
5 4 5 1 2 2 3 3 4 4 1
Output
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:
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 .
题意:
给出一幅图, 求再加几条边能够使首都都能够到达所有城市。 。。
先用targan+ 缩点, 将所有的连通分量缩成一个点, 统计除了首都所在的缩点入度为0的个数。 。
代码如下:
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
const int maxn=5e3+5;
vector<int>ve[maxn];
int ccnc[maxn],in[maxn];
stack<int>s;
int n,m,ss;
int low[maxn],dfn[maxn];
int tot,ccnum,sum=0;
void init()
{
ccnum=tot=0;
memset (in,0,sizeof (in));
memset (low,0,sizeof(low));
memset (dfn,0,sizeof(dfn));
memset (ccnc,0,sizeof(ccnc));
}
void targan (int x)
{
low[x]=dfn[x]=++tot;
s.push(x);
for (int i=0;i<ve[x].size();i++)
{
int v=ve[x][i];
if(!dfn[v])
{
targan(v);
low[x]=min(low[x],low[v]);
}
else if(!ccnc[v])
low[x]=min(low[x],dfn[v]);
}
if(dfn[x]==low[x])
{
ccnum++;
while (1)
{
int now=s.top();
s.pop();
ccnc[now]=ccnum;
if(now==x)
break;
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&ss);
init();
while (m--)
{
int x,y;
scanf("%d%d",&x,&y);
ve[x].push_back(y);
}
for (int i=1;i<=n;i++)
if(!dfn[i])
targan(i);
for (int i=1;i<=n;i++)
for (int j=0;j<ve[i].size();j++)
{
int v=ve[i][j];
if(ccnc[i]!=ccnc[v])
in[ccnc[v]]++;
}
int temp=ccnc[ss];
for (int i=1;i<=ccnum;i++)
{
if(!in[i]&&i!=temp)
sum++;
}
printf("%d\n",sum);
return 0;
}
上一篇: 【CodeForces】【搜索】999E Reachability from the Capital
下一篇: CodeForces ~ 999E ~ Reachability from the Capital (思维 + 图的DFS)
推荐阅读