题目描述

JYY 最近痴迷于图的强连通性，所以对于任何有向图，JYY 都希望增加一些边使得这个图变成强连通图。JYY现在得到了一个 n 个点 m 条边的有向图，所有点从 1 到 n 编号。

JYY 想知道：

在给定的图中，最多能选出多少个点，使得这些点在原图中两两可达？

在给定的图中，最少增加多少条边，可以使得这个图变成强连通图？

其中，一个有向图$ G(V,E)$是强连通的，当且仅当任意顶点 a,b$\in$ V,a$\neq$ b之间都存在 a$\to$ b 和 b $\to$ a 的路径。

输入样例

4 3
1 4
2 3
2 4

输出样例

1
2 

样例说明

对于第一个问题，无法选出互相连通两个点，答案为$ 1$。

对于第二个问题，一种加边数最小的方案为 $(3,1)$和 $(4,2)$，答案为 $2$。

分析

第一问是求一个连通图中的最大连通子图，可以用tarjan直接求出。
第二问，如果一个图是强联通图的话，那么它的每个点的出度入度都至少为1，所以我们需要统计出所有点的出入度，之后把出度为0的点统计一下，入度为0的点统计一下，两者取最大即可。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10,M = 3e5+10;
int n,m;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],timestamp;
int stk[N],top;
int id[N],scc_cnt,siz[N];   //id[]每个点位于哪个连通分量，siz[]每个连通分量大小
bool in_stk[N];
int din[N],dout[N];
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int u)
{
    dfn[u]=low[u]=++timestamp;
    in_stk[u]=true;
    stk[++top]=u;

    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }
        else if(in_stk[j])
            low[u]=min(low[u],dfn[j]);
    }

    if(dfn[u]==low[u])
    {
        ++scc_cnt;
        int y;
        do{
            y=stk[top--];
            in_stk[y]=false;
            id[y]=scc_cnt;
            siz[scc_cnt]++;
        }while(y!=u);
    }
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d",&n,&m);

    int a,b;
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&a,&b);
        add(a,b);
        dout[a]++,din[b]++;
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i])
            tarjan(i);

    if(!scc_cnt) puts("1");
    else{
        int ans=0;
        for(int i=1;i<=scc_cnt;i++)     //遍历所有连通分量
        {
            ans=max(ans,siz[i]);        //找最大连通分量
        }
        cout<<ans<<endl;
    }

    int co1=0,co2=0;
    for(int i=1;i<=n;i++)
    {
        if(din[i]==0) co1++;        //统计入度为0的点
        if(dout[i]==0) co2++;       //统计出度为0的点
    }
    cout<<max(co1,co2)<<endl;
    return 0;
}