题解：P15508 [CEOI 2012] 网络 / Network

· · 题解

传送门

P15508 [CEOI 2012] 网络 / Network

题意

一个有向图，求：

  1. 每个节点的可达节点的数量；

  2. 加入一些有向边，使任意一对节点 u,v 有且只有一条路径可以从 u 到达 v 所需的最小路径数量并给出路径。

思路

第一问是比较简单的，首先显然不能对每一个点统计可达数，考虑将原图缩点，缩点后的点权值为原来的环的大小，缩点后是一棵有向有根树，从根节点开始向下递归，可以发现每个（缩点后的）点的可达数就是它的子树权值（包括自己），当然每个缩点后的点中包含的点的可达数都是相同的。（结果我模拟赛缩点写炸了？）

第二问的话，因为边双已经联通，不能再加边，所以问题变成了：在一棵有向有根树上加最少的边，使得整张图满足任意两点之间至多一条有向路径，并且整体强连通。

可以发现，一条边最多只能出现在一个环上，因为如果出现在了多个环上那么必定会有两点之间有多条路径。那么显然可以用第一个儿子剖分（其他也行）将缩点后的树划分为若干条链，每条链的链尾连一条到链首的边即可，显然最优。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,r,tot,id,dfn[100001],low[100001],col[100001],co,siz[100001],ans[100001],son[100001];
bool is[1000005],vis[100001];
vector<pair<int,int>> to[100001],add;
vector<int> d[100001],nw[100001];
void tarjan(int x,int f)
{
    dfn[x]=low[x]=++tot;
    for(int i=0;i<(int)to[x].size();i++)
    {
        int y=to[x][i].first;
        if(to[x][i].second==f||to[x][i].second==(f^1))
            continue;
        if(!dfn[y])
        {
            tarjan(y,to[x][i].second);
            low[x]=min(low[x],low[y]);
            if(low[y]>dfn[x])
                is[to[x][i].second]=is[to[x][i].second^1]=1;
        }
        else
            low[x]=min(low[x],dfn[y]);
    }
}
void ecc(int x)
{
    col[x]=co;
    d[co].push_back(x);
    for(int i=0;i<(int)to[x].size();i++) 
    {
        int y=to[x][i].first;
        if((!is[to[x][i].second])&&(!col[y])) 
            ecc(y);
    }
}
void dfs(int x)
{
    siz[x]=d[x].size();
    for(int i=0;i<(int)nw[x].size();i++) 
    {
        int y=nw[x][i];
        dfs(y);
        siz[x]+=siz[y];
    }
    ans[x]=siz[x];
}
void dfs2(int x,int t)
{
    vis[x]=1;
    for(int i=0;i<(int)to[x].size();i++)
    {
        int y=to[x][i].first;
        if(vis[y]||(to[x][i].second%2==1))
            continue;
        if(col[x]==col[y])//属于同一个边双肯定不连，但另一个点或许还需要连边
            dfs2(y,y);
        else
        {
            if(!son[x])//没有儿子则成为第一个儿子
            {
                son[x]=y;
                dfs2(y,t);//继续走下去
            }
            else
                dfs2(y,x);//开一个新的链
        }
    }
    if(!son[x]&&x!=t)
        add.push_back({x,t});//连接链尾和链首
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>r;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        to[u].push_back({v,id});
        to[v].push_back({u,id^1});
        id+=2;
    }
    tarjan(r,-1);
    for(int i=1;i<=n;i++)
        if(!col[i])
        {
            co++;
            ecc(i);//标记每个点所在的连通块
        }
    for(int i=1;i<=n;i++)
        for(int j=0;j<(int)to[i].size();j++)
        {
            int v=to[i][j].first;
            if(to[i][j].second%2==0&&col[i]!=col[v])
                nw[col[i]].push_back(col[v]);//按缩点过后的建一个新图
        }
    dfs(col[r]);//统计第一问答案
    for(int i=1;i<=n;i++)
        cout<<ans[col[i]]<<' ';
    cout<<'\n';
    dfs2(r,r);//第一个儿子剖分
    cout<<(int)add.size()<<'\n';
    for(auto i:add)
        cout<<i.first<<' '<<i.second<<'\n';
    return 0;
}