题目大意:N(2<N<100)各学校之间有单向的网络,每个学校得到一套软件后,可以通过单向网络向周边的学校传输,问题1:初始至少需要向多少个学校发放软件,使得网络内所有的学校最终都能得到软件。2,至少需要添加几条传输线路(边),使任意向一个学校发放软件后,经过若干次传送,网络内所有的学校最终都能得到软件。
具体算法:先用tarjam求出有向图所有的强连通分量,然后将所有的强连通分量缩成一个点(缩点),这样原来的有向图就缩成了一个DAG图(有向无环图);因为两个强连通合并必然是出度为0的连接入度为0的点,所以要解决掉入度为0,和出度为0的点,所以答案是这两个的最大值用2个数组分别记录新生成的DAG图中的每个顶点(包括原来的顶点和强连通分量的缩点)是否有出边和入边,最后遍历每个顶点,如果没有入边,则ans1++;如果没有出边,ans2++。最后所求即为ans1和max(ans1,ans2)。
#include <cstdio>
#include <iostream>
#include <vector>
#include <stack>
#include <cmath>
#include <cstring>
using namespace std;
const int N=102;
const int M=50012;
int n,m;
int scc;//强连通分量
int index;//每个节点的dfs访问次序编号
int dfn[N];//标记结点i的dfs访问次序
int low[N];//记录节点u或u的子树中的所有节点的最小标号
int fa[N];//属于哪个分支
bool instack[N];//是否在栈中
int in[N];
int out[N];//出度
vector<int>p[N];
stack <int>s;
void tarjan(int u)
{
dfn[u]=low[u]=++index;
s.push(u);
instack[u]=true;
for (int j=0;j<p[u].size();j++)
{
int v=p[u][j];
if(dfn[v]==0)//未曾访问过
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(instack[v])
{
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u])
{
scc++;
while(1)
{
int tmp=s.top();
s.pop();
instack[tmp]=0;
fa[tmp]=scc;
if(tmp==u)
break;
}
}
}
void solve()
{
scc=index=0;
memset(dfn,0,sizeof(dfn));
for (int i=1;i<=n;i++)
{
if (!dfn[i])
tarjan(i);
}
if(scc==1)
{
printf("1\n");
printf("0\n");
}
else
{
memset(in,0,sizeof(in));
memset(out,0,sizeof(out));
for (int i=1;i<=n;i++)
{
for(int j=0;j<p[i].size();j++)
{
int u=fa[i];
int v=fa[p[i][j]];
if(u!=v)
{
out[u]++;
in[v]++;
}
}
}
int outn=0;
int inn=0;
for(int i=1;i<=scc;i++)
{
if(in[i]==0)inn++;
if(out[i]==0)outn++;
}
printf("%d\n",inn);
printf("%d\n",max(outn,inn));
}
}
int main()
{
cin>>n;
{
int k=0;
for(int i=1;i<=n;i++)
{
int a;
while(1)
{
scanf("%d",&a);
if(!a)break;
p[i].push_back(a);
}
}
solve();
}
return 0;
}