题解：P7251 [JSOI2014] 强连通图

ksmgxeh · 2025-07-13 14:55:26 · 题解

强连通分量模板题。

首先 tarjan 求出原图中所有的强连通分量。对于第一问，因为每个强连通分量中的点两两可达，所以答案即为最大的强连通分量大小。

对于第二问。将每个强连通分量缩成一个点后，记入度为零的个数为 in，出度为零的点的个数为 out。如果 in<out，对每个入度为零的点再连条边到出度为零的即可。反之亦然。所以答案为 \max(in,out)。

注意特判原图只有一个强连通分量时，第二问不用多连任何边，所以答案为零。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+5;
int n,m; 
int low[N],dfn[N],stk[N],ins[N],siz[N],scc[N],idx,top,id,in[N],out[N];
vector<int> e[N];

void tarjan(int x){
    dfn[x]=low[x]=++idx,stk[++top]=x,ins[x]=1;
    for(int i=0;i<e[x].size();i++){
        int y=e[x][i];
        if(!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }else if(ins[y])
            low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x]){
        int y; id++;
        do{
            y=stk[top--];
            ins[y]=0,siz[id]++;
            scc[y]=id;
        }while(x!=y);
    }
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v; cin>>u>>v;
        e[u].push_back(v);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);
    for(int x=1;x<=n;x++){
        for(int i=0;i<e[x].size();i++){
            int y=e[x][i];
            if(scc[x]!=scc[y]){
                in[scc[y]]++,out[scc[x]]++;
            }
        }
    }
    if(id==1){
        cout<<siz[1]<<endl<<0;
        return 0;
    }
    int c=0,c1=0,c2=0;
    for(int i=1;i<=id;i++){
        c=max(c,siz[i]);
        if(!in[i]) c1++;
        if(!out[i]) c2++;
    }
    cout<<c<<endl<<max(c1,c2);
    return 0;
}