2022-2023 ICPC Brazil Subregional Programming Contest - H - Helping the Transit 缩点+DAG转强连通_2023-2024 icpc brazil subregional programming cont

H - Helping the Transit

time limit per test 0.25 seconds
memory limit per test1024 megabytes
inputstandard input
outputstandard output

题目描述

The president of Nlogonia decided, by decree, that all the streets of Nlogonia should be one-way. Due to the lack of knowledge of elementary science, there was no proper planning for the changes. After the new system came in place, people would not be able to go to work, or would not be able to return home from work, for example. As a result, there was chaos and riots in lots of cities.

The president was impeached and the new administration of the country hired a team of scientists to solve the problem. In turn, the committee hired you, an expert in complexity of algorithms, to help them with the efficient computation of solutions.

So, for each city, you are given the reference points of the city, and the one-way streets, each of which connects two reference points. Your task is to determine the minimum number of one-way bridges that must be built in order to have full connectivity in the city. Each bridge should also connect two reference points.

输入描述

The first line of the input contains two integers, N and M (1≤N≤104,0≤M≤106), where N is the number of reference points and M is the number of streets. Each one of the next M lines contains two integers, R and S, 1≤R,S≤N, R≠S, that corresponds to a street connecting R to S, so that every vehicle in that street must move away from R, towards S.

输出描述

Your program must print a single line containing the minimum number of bridges that are necessary to make the inhabitants happy.

题意

给定一张有向图 求需要添加几条有向边能使图变为强连通图

思路

先缩点将有向图转化为 DAG 图，然后统计出度为0的点以及入度为0点 添加其最大值条有向边即可转化为强连通图

Code

#include<bits/stdc++.h>
using namespace std;
#define __T int csT;scanf("%d",&csT);while(csT--)
const int mod=1e9+7;
const int maxn=1e4+3;
const int maxm=1e6+3;

int n,m,cnt,flcnt;
int u[maxm],v[maxm];
struct node{
    int to,nx;
}e[maxm],re[maxm];
int h[maxn],rh[maxn],vis[maxn],st[maxn],fr[maxn];
int rd[maxn],cd[maxn];
void dfs1(int at)
{
    if(vis[at]==1)return;
    vis[at]=1;
    for(int i=h[at];~i;i=e[i].nx)
    {
        dfs1(e[i].to);
    }
    st[++cnt]=at;
}
void dfs2(int at,int id)
{
    if(vis[at]==2)return;
    vis[at]=2;
    fr[at]=id;
    for(int i=rh[at];~i;i=re[i].nx)
    {
        dfs2(re[i].to,id);
    }
}
inline void sol()
{
    scanf("%d%d",&n,&m);
    memset(h,-1, sizeof h);
    memset(rh,-1, sizeof rh);
    memset(vis,0,sizeof vis);
    cnt=0;
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&u[i],&v[i]);
        e[++cnt].to=v[i];
        e[cnt].nx=h[u[i]];
        h[u[i]]=cnt;
        re[cnt].to=u[i];
        re[cnt].nx=rh[v[i]];
        rh[v[i]]=cnt;
    }
    cnt=0;
    for(int i=1;i<=n;++i)
    {
        if(vis[i]==0)dfs1(i);
    }
    flcnt=0;
    for(int i=n;i>=1;--i)
    {
        if(vis[st[i]]==1)
        {
            dfs2(st[i],++flcnt);
        }
    }
    if(flcnt==1)
    {
        puts("0");
        return;
    }
    memset(rd,0,sizeof rd);
    memset(cd,0,sizeof cd);
    for(int i=1;i<=m;++i)
    {
        if(fr[u[i]]!=fr[v[i]])
        {
            ++cd[fr[u[i]]];
            ++rd[fr[v[i]]];
        }
    }
    int rd_0=0,cd_0=0;
    for(int i=1;i<=flcnt;++i)
    {
        if(rd[i]==0)++rd_0;
        if(cd[i]==0)++cd_0;
    }
    printf("%d\n",max(rd_0,cd_0));
}

int main()
{
    //__T
    sol();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94