题目描述

给你一张有向图，求：

1. 图中最大强连通分量的大小
2. 至少加多少条边才能够让其变成一张强连通图
3. 一种加边的方案

数据范围

$n \leq 10^4,m \leq 2 \times 10^5$，至少要加的边数小于等于 1000.

题目分析

首先 tarjan 跑一次缩点，轻松求出第一问（以下的 “点” 皆表示缩点后的点）
第二问的答案是 max(只有入度为 0 的点数，只有出度为 0 的点数）+孤点（出入度都为 0）（另外，如果本图就是强连通图，那当然答案是 0）
那么这是为什么呢，看了构造方法就知道了。

加边方案怎么求呢？
随机化瞎搞，请 boshi 同学开始 TA 的表演
贪心瞎搞，请 xzy 同学开始 TA 的表演
二分图匹配。

首先，每个入度为 0 的点都要有一个点到它，每个出度为 0 的点都要到一个点，这种性质让我们联想到美丽的二分图。我们先把孤点扔掉，然后建立一个二分图，一边为出度为 0 的点，一边为入度为 0 的点，然后如果某一个出度为 0 的点可以到达入度为 0 的点，它们之间就有一条边。用匈牙利算法跑一次匹配。

然后匹配完之后，大概是这样的：
$a_1$——>$b_1$
$a_2$——>$b_2$
…
$a_n$——>$b_n$
连边：
$b_1$——>$a_2$
$b_2$——>$a_3$
…
$b_n$——>$a_1$
这样就形成了一个环，环当然是强连通分量。然后没有匹配上点的那些 single dog 们呢，如果它是出度为 0 的点，那么一定有一个环上的点到它。如果它是入度为 0 的点，那么一定到一个环上的点。所以我们只要在它们之间任意连一些边就强连通了。

至于孤点，将环从某处断开，接上去即可。

注意全是孤点的情况。

代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int read() {
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q;
}
const int N=10005,M=200005;
int n,m,tot,now,top,cnt,ans1;
int h[N],ne[M],to[M],dfn[N],low[N],st[N],ins[N];
int col[N],bj[N],sz[N],cd[N],rd[N];

void add(int x,int y) {to[++tot]=y,ne[tot]=h[x],h[x]=tot;}
void tarjan(int x) {//tarjan 大法好
    dfn[x]=low[x]=++now,st[++top]=x,ins[x]=1;
    for(RI i=h[x];i;i=ne[i])
        if(!dfn[to[i]]) tarjan(to[i]),low[x]=min(low[x],low[to[i]]);
        else if(ins[to[i]]) low[x]=min(low[x],dfn[to[i]]);
    if(dfn[x]==low[x]) {
        ++cnt,bj[cnt]=x;
        while(st[top]!=x)
            col[st[top]]=cnt,++sz[cnt],ins[st[top]]=0,--top;
        col[x]=cnt,++sz[cnt],ins[st[top]]=0,--top;
    }
}

vector<int> G[N],B[N];
int r0[N],c0[N],QAQ[N],vis[N],cp[N],QvQ[N],dog[N],cg[N];
int js1,js2,js3,orz,STO;
void dfs(int x,int st) {//寻找每一个入度为 0 点可达的出度为 0 点
    if(cd[x]==0) B[st].push_back(x);
    for(RI i=0;i<cd[x];++i)
        if(cg[G[x][i]]!=st) cg[G[x][i]]=st,dfs(G[x][i],st);
}
int Nico(int x) {//二分图匹配
    for(RI i=0;i<B[x].size();++i) 
        if(!vis[B[x][i]]) {
            vis[B[x][i]]=1;
            if(!cp[B[x][i]]||Nico(cp[B[x][i]])) {
                cp[B[x][i]]=x,cp[x]=B[x][i];
                return 1;
            }
        }
    return 0;
}
void work() {
    for(RI i=1;i<=cnt;++i)
        if(!rd[i]&&!cd[i]) QAQ[++js3]=i;
        else if(!rd[i]) r0[++js1]=i;
        else if(!cd[i]) c0[++js2]=i;
    printf("%d\n",max(js1,js2)+js3);
    for(RI i=1;i<=js1;++i) dfs(r0[i],r0[i]);
    for(RI i=1;i<=js1;++i) {
        for(RI j=1;j<=js2;++j) vis[c0[j]]=0;
        Nico(r0[i]);
    }
    for(RI i=1;i<=js1;++i)
        if(!cp[r0[i]]) dog[++STO]=r0[i];//处理单身狗
        else QvQ[++orz]=r0[i];
    for(RI i=1;i<=js2;++i)
        if(!cp[c0[i]]) {
            if(STO) printf("%d %d\n",bj[c0[i]],bj[dog[STO]]),--STO;//优先单身狗与单身狗牵手
            else printf("%d %d\n",bj[c0[i]],bj[r0[1]]);
        }
    while(STO) printf("%d %d\n",bj[c0[1]],bj[dog[STO]]),--STO;//乱连边
    if(orz) {//断开环接上孤点
        for(RI i=1;i<orz;++i)
            printf("%d %d\n",bj[cp[QvQ[i]]],bj[QvQ[i+1]]);
        int las=cp[QvQ[orz]];
        for(RI i=1;i<=js3;++i) printf("%d %d\n",bj[las],bj[QAQ[i]]),las=QAQ[i];
        printf("%d %d\n",bj[las],bj[QvQ[1]]);
    }
    else {//只有孤点的情况
        for(RI i=1;i<js3;++i) printf("%d %d\n",bj[QAQ[i]],bj[QAQ[i+1]]);
        printf("%d %d\n",bj[QAQ[js3]],bj[QAQ[1]]);
    }
}

int main()
{
    freopen("scg.in","r",stdin);
    freopen("scg.out","w",stdout);
    int x,y;
    n=read(),m=read();
    for(RI i=1;i<=m;++i) x=read(),y=read(),add(x,y);
    for(RI i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
    for(RI i=1;i<=cnt;++i) ans1=max(ans1,sz[i]);
    printf("%d\n",ans1);
    if(cnt==1) {puts("0");return 0;}
    for(RI i=1;i<=n;++i)
        for(RI j=h[i];j;j=ne[j])
            if(col[i]!=col[to[j]]) G[col[i]].push_back(col[to[j]]);
    for(RI i=1;i<=cnt;++i) {
        sort(G[i].begin(),G[i].end());
        G[i].erase(unique(G[i].begin(),G[i].end()),G[i].end());
        cd[i]=G[i].size();
        for(RI j=0;j<cd[i];++j) ++rd[G[i][j]];
    }
    work();
    return 0;
}