模拟赛题讲解[6]

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

题目描述：

给定一个连通无向图 \(G=(V,E)\) ，其中顶点个数 \(\vert V\vert=n\) ，边数 \(\vert E\vert=m\) 。顶点编号为 \(1-n\) ，边的编号为 \(1-m\) ，第 \(i\)条边连接顶点 \(a_i\) 和 \(b_i\)。输入保证图中不存在重边。

你现在需要对图中的每条边定向: 对于原图中的每条无向边 \((u,v)\)，你需要选择将它变为有向边 \((u,v)\)或者有向边 \((v,u)\).

对于图 \(G\)中的每个顶点 \(v\in V\)，定义 \(r_v\) 为将图定向之后 \(v\) 能够到达的顶点个数，你需要选择一种定向使得最大化 \(\min\limits_{v \in V}r_v\)，也就是最大化所有 \(r_v\) 的最小值。输出这个最大化的值。

输入格式：

输入第一行包含 \(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：

数据范围：

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

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

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

题解：

不难发现，一个边双连通分量，一定可以通过给边标向变成强连通分量

而这道题的答案，其实就是所有边双连通分量中最大的那个所包含的结点数

证明：

首先我们先证明答案至多为 \(\max\left\{|V^{\prime}_i|\right\}\)

不难发现，我们对所有的桥（割边）标向后，一定会有一个边双无出边

而这个边双的大小 \(|V_i^{\prime}|\) 会影响全局的答案，于是要贪心的使这个大小取最大。证毕。

然后我们证明答案至少为 \(\max\left\{|V_i^{\prime}|\right\}\)

以这个最大的边双为根节点（边双缩点后一定是棵树），其他的结点全部往父亲指

这样每个边双至少可以走到这个满足 \(|V^{\prime}|=\max\left\{|V_i^{\prime}|\right\}\) 的 \(V^{\prime}\) 。证毕。

~~你敢信这段东西我花了3min速记的，不然会忘记老师讲的证明的，2333~~

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

代码：

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

int n,m,top,pos=1,ecnt,dfncnt;
int dfn[N],low[N],head[N],stk[N],sz[N],ecc[N];
struct Edge{int u,v,next;}e[M<<1];
void addEdge(int u,int v)
{
    e[++pos]={u,v,head[u]};
    head[u]=pos;
}
void tarjan(int u,int in_edge)
{
    dfn[u]=low[u]=++dfncnt;
    stk[++top]=u;
    for(int i=head[u]; i; i=e[i].next)
    {
        int v=e[i].v;
        if(!dfn[v])
        {
            tarjan(v,i);
            low[u]=min(low[u],low[v]);
        }else if(i!=(in_edge^1))
            low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u])
    {
        ecc[u]=++ecnt; ++sz[ecnt];
        while(stk[top]!=u)
            ecc[stk[top--]]=ecnt,++sz[ecnt];
        --top;
    }
}
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;
        addEdge(u,v); addEdge(v,u);
    }
    for(int i=1; i<=n; i++)
        if(!dfn[i]) top=0,tarjan(i,0);
    int res=0;
    for(int i=1; i<=ecnt; i++)
        res=max(res,sz[i]);
    cout << res << '\n';
    return 0;
}