P2746题解

问题：
本题描述了一个有向图模型：
每个学校是一个节点
学校间的分享关系构成有向边（如果 a 分享给 b，则存在 a→b 的边）
需要解决两个独立的问题：
1.至少需要向几个学校发放软件，才能让所有学校都获得软件
相当于找到最少数量的起点，使得从这些起点出发可以到达所有节点
2.至少需要添加多少条边，使得整个图变成强连通图
使得无论从哪个学校发放软件，所有学校都能获得软件
思路：
使用 Tarjan 算法缩点后：
对于问题1：
缩点后得到 DAG（有向无环图）
需要发放软件的学校数量 = DAG 中入度为 0 的强连通分量数量
因为入度为 0 的点没有其他点能到达它，必须作为起点
对于问题2：
需要使 DAG 变成强连通图
最少需要添加的边数=max(入度为0的点数, 出度为0的点数)
特殊情况：如果整个图已经是一个强连通分量，答案为 0
算法：
使用 Tarjan 算法求强连通分量
对每个未访问的节点进行 DFS
维护 dfn（访问顺序）和 low（能回溯到的最早节点）
当 low[u] == dfn[u] 时，找到一个强连通分量
缩点并统计度数
对原图的每条边，如果两端点在不同分量，则在缩点后的图中添加边
统计每个分量的入度和出度
计算答案
问题1：入度为0的分量个数
问题2:如果只有一个分量：0
否则：max(入度为0的个数, 出度为0的个数)
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,tot,tp,cl;
vector<int>g[N];
int dfn[N],low[N],st[N],col[N],sz[N];
int ind[N],oud[N];
void tarjan(int u){
dfn[u]=low[u]=++tot;
st[++tp]=u;
for(int v:g[u]){
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(!col[v])low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]){
col[u]=++cl;
while(st[tp]!=u){
col[st[tp]]=cl;
tp--;
}
tp--;
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
int x;
cin>>x;
while(x){
g[i].push_back(x);
cin>>x;
}
}
for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
for(int u=1;u<=n;u++){
for(int v:g[u]){
if(col[u]!=col[v]){
ind[col[v]]++;
oud[col[u]]++;
}
}
}
int ans1=0,ans2=0;
for(int i=1;i<=cl;i++){
if(!ind[i])ans1++;
if(!oud[i])ans2++;
}
cout<<ans1<<endl;
if(cl==1)cout<<0;
else cout<<max(ans1,ans2);
return 0;
}