模拟赛题讲解[7]

来自 Roundgod 2022-07-27 noi.ac #2682

题目描述：

给定一个有向图 \(G=(V,E)\) ，其中顶点个数 \(\vert V\vert=n\) ，边数 \(\vert E\vert=m\) 。顶点编号为 \(1-n\) ，边的编号为 \(1-m\) ，第 \(i\) 条边连接顶点 \(a_i\) 和 \(b_i\)。

你最少需要添加多少条有向边，才能使得能够从 \(1\) 到达所有顶点?

输入格式：

输入第一行包含 \(2\)个整数 \(n,m\)，分别表示图的顶点数和图的边数。

接下来 \(m\)行，每行包含两个整数 \(a_i,b_i(1\leq a_i,b_i\leq n,a_i\neq b_i)\) ，表示第 \(i\) 条边从顶点 \(a_i\) 指向顶点 \(b_i\)。

输入保证图中不存在重边和自环。

输出格式：

在一行中输出一个整数，表示最少需要添加的有向边条数。

输入1：

输出1：

输入2：

输出2

数据范围：

对于 \(50\%\) 的数据，\(1\leq n\leq 5000,~1\leq m\leq 5000\)

对于 \(100\%\) 的数据，\(1\leq n\leq 2\times 10^5,~1\leq m\leq 2\times 10^5\)

题解：

先强连通分量缩点一下，正确性显然。

然后对于 \(1\) 本来就能到的结点，根本不用管

对于 \(1\) 不能到的结点，我们只要连入度为 \(0\) 的那些就行了

因为连了那些点，其他点都可以走到

时间复杂度 \(O(n+m)\)

我的考场代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
#include <queue>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(2e5+15)

bool vis[N];
int n,m,idx,scnt,dfn[N],in[N],scc[N];
vector<int> g1[N],g2[N];
void addEdge1(int u,int v)
{
    g1[u].push_back(v);
    g2[v].push_back(u);
}
void dfs1(int u)
{
    vis[u]=1;
    for(int v : g1[u])
        if(!vis[v]) dfs1(v);
    dfn[++idx]=u;
}
void dfs2(int u,int id)
{
    scc[u]=id;
    for(int v : g2[u])
        if(!scc[v]) dfs2(v,id);
}
void kosaraju()
{
    for(int i=1; i<=n; i++)
        if(!vis[i]) dfs1(i);
    scnt=0;
    for(int i=n; i>=1; i--)
        if(!scc[dfn[i]])
        {
            ++scnt;
            dfs2(dfn[i],scnt);
        }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i=1,u,v; i<=m; i++)
    {
        cin >> u >> v;
        addEdge1(u,v);
    }
    kosaraju();
    for(int i=1; i<=n; i++)
        for(int j : g1[i])
        {
            int u=scc[i],v=scc[j];
            if(u!=v) ++in[v];
        }
    int res=0;

    // for(int i=1; i<=n; i++)
    //     cout << scc[i] << " \n"[i==n];

    for(int i=1; i<=scnt; i++)
        if(i!=scc[1]) res+=(in[i]==0);
    cout << res << '\n';
    return 0;
}