Luogu P2812 校园网络
几所不同的学校希望在一个有向图网络上共享一个软件，共有n所学校（n<=10000）已知他们实现设计好的网络共m条线路，为了保证高速，网络是单向的。 现在请你告诉他们至少选几所学校作为共享软件的母机，能使每所学校都可以用上。 再告诉他们至少要添加几条线路能使任意一所学校作为母机都可以使别的学校使用上软件。
思路
第一问就是跑tarjan，然后答案就是强连通分量个数第二问相当于一个DAG，求把它变成强连通分量需要加的边，我们考虑在新图中，只需要把出度为零的点连向入度为零的点
code
// 2812
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=10010;
const int M=5000100;
struct node
{
int v,nxt;
}edge[M];
int head[N],cnt;
void add(int u,int v)
{
cnt++;
edge[cnt].v=v;
edge[cnt].nxt=head[u];
head[u]=cnt;
}
int t,dfn[N],low[N];
int stack[N],top;
bool instack[N];
int belong[N],cc;
int n;
void dfs(int now)
{
t++;
dfn[now]=low[now]=t;
stack[++top]=now;
instack[now]=true;
for(int i=head[now];i;i=edge[i].nxt)
{
int v=edge[i].v;
if(!dfn[v])
{
dfs(v);
low[now]=min(low[now],low[v]);
}
else
{
if(instack[v])
low[now]=min(low[now],dfn[v]);
}
}
if(low[now]==dfn[now])
{
cc++;
while(stack[top]!=now)
{
belong[stack[top]]=cc;
instack[stack[top]]=false;
top--;
}
belong[now]=cc;
instack[now]=false;
top--;
}
}
int in[N],out[N];
void tarjan()
{
for(int i=1;i<=n;i++)
{
if(!dfn[i])
{
dfs(i);
}
}
for(int u=1;u<=n;u++)
{
for(int i=head[u];i;i=edge[i].nxt)
{
int v=edge[i].v;
if(belong[u]!=belong[v])
{
out[belong[u]]++;
in[belong[v]]++;
}
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
int j;
while(cin>>j&&j)
{
add(i,j);
}
}
tarjan();
int ans1=0,ans2=0;
for(int i=1;i<=cc;i++)
{
if(!in[i]) ans1++;
if(!out[i]) ans2++;
}
cout<<ans1<<endl;
cout<<max(ans1,ans2)<<endl;
return 0;
}
