（强连通分量）洛谷 P2812 校园网络（加强版）题解

这一题是洛谷 P2746 的加强版，第 $1$ 问就是 P2002 和 P2835。

题意

共有 $n$ 所学校已知他们实现设计好的网络共 $m$ 条线路，为了保证高速，网络是单向的。现在请你告诉他们至少选几所学校作为共享软件的母机，能使每所学校都可以用上。再告诉他们至少要添加几条线路能使任意一所学校作为母机都可以使别的学校使用上软件。

$1\le$ 边数 $\le 5000000$，$1\le n\le 10000$ 。

思路

用 tarjan 求强连通分量（scc）的代码其实很好写，求强连通分量多用于缩点。此处将不会详细解析 tarjan-scc 算法，如有需要请移步 OI-WIKI。

贴一个板子：

ll ti,dfn[N],low[N],top,stk[N];
ll scccnt,sccno[N];
void tarjan(ll u)
{dfn[u]=low[u]=++ti;stk[top++]=u;for(int i=head[u];i;i=e[i].next){ll v=e[i].to;if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}else if(!sccno[v])low[u]=min(low[u],dfn[v]);}if(dfn[u]==low[u]){scccnt++;while(1){ll tem=stk[--top];sccno[tem]=scccnt;if(u==tem)break;}}
}

其实大多数题目的思维难度都在图论建模上。

我们将每个 scc 缩点，对于每条边我们连接两端 scc 的有向边（同 scc 就不用）看看哪个 scc 没有入度，这个 scc 的其中一个节点就可以成为母机。我们就解决了第 $1$ 问。

对于第 $2$ 问，我们再求一个没有出度的 scc 数，对于没有入度和出度的末端点，我们取个数更多的，将没有入度的全部连上没有出度的。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=5e6+9;
ll n,m;
bool in[N],out[N];
struct bian
{ll u,v;
}b[N];
ll idx,head[N];
struct edge
{ll to,next;
}e[N<<1];
void addedge(ll u,ll v)
{idx++;e[idx].to=v;e[idx].next=head[u];head[u]=idx;
}
ll ti,dfn[N],low[N],top,stk[N];
ll scccnt,sccno[N];
void tarjan(ll u)
{dfn[u]=low[u]=++ti;stk[top++]=u;for(int i=head[u];i;i=e[i].next){ll v=e[i].to;if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}else if(!sccno[v])low[u]=min(low[u],dfn[v]);}if(dfn[u]==low[u]){scccnt++;while(1){ll tem=stk[--top];sccno[tem]=scccnt;if(u==tem)break;}}
}
int main()
{scanf("%lld",&n);for(int i=1;i<=n;i++){while(1){ll v;scanf("%lld",&v);if(v==0)break;b[++m]=(bian){i,v};addedge(i,v);}}for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);for(int i=1;i<=m;i++){ll su=sccno[b[i].u],sv=sccno[b[i].v];if(su==sv)continue;in[sv]=1;out[su]=1;}ll ans1=0,ans2=0;for(int i=1;i<=scccnt;i++){ans1+=(!in[i]);ans2+=(!out[i]);}printf("%lld\n",ans1);if(scccnt==1)puts("0");else printf("%lld",max(ans1,ans2));return 0;
}