POJ1236 network of schools

时间:2022-10-26 17:08:27

100个学校,有单向网络连接,从而分享软件。

问题一:几个学校得到软件就可使所有学校都得到?

问题二:再加几条单向网络可以使得“任意学校得到软件,就可使得所有学校都有软件”?

——————————————————————————————————————————————————————————

强连通分量内部可做到“一点得,全部得”,从而可以看做一个点,所以,缩点,得到有向无环图。

在图中,入读为0的点因为无人与他分享,所以必须直接获得——问题一答案。

想要“一点得,全部得”,就要全部点成为一个强连通分量,加边的多少由入读为0的点数和出度为0的点数的最大值决定。——问题二答案

注意:如果所有点本身就是强连通分量,需要特判。

——————————————————————————————————————————————————————————

 #include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<stack> using namespace std;
const int maxn=;
int n;
struct edge
{
int u,v,next;
}e[],ee[];
int head[],headd[],js,jss;
int dfsn[],low[],visx;
stack<int>st;
bool ins[];
int chudu[],rudu[];
int sshu,belong[];
void addage(int u,int v,edge e[],int head[],int &js)
{
e[++js].u=u;e[js].v=v;
e[js].next=head[u];head[u]=js;
}
void tarjan(int u)
{
dfsn[u]=low[u]=++visx;
st.push(u);
ins[u]=;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(dfsn[v]==)
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(ins[v] && low[u]>dfsn[v])low[u]=dfsn[v];
}
if(dfsn[u]==low[u])
{
sshu++;
int tp;
do
{
tp=st.top();
st.pop();
ins[tp]=;
belong[tp]=sshu;
}
while(tp!=u);
}
}
int main()
{
scanf("%d",&n);
for(int v,i=;i<=n;i++)
{
while(scanf("%d",&v)== && v!=)
{
addage(i,v,e,head,js);
}
}
for(int i=;i<=n;i++)
if(dfsn[i]==)tarjan(i);
for(int i=;i<=js;i++)
{
int u=e[i].u,v=e[i].v;
if(belong[u]!=belong[v])
{
addage(belong[u],belong[v],ee,headd,jss);
chudu[belong[u]]++;rudu[belong[v]]++;
}
}
int chudu0=,rudu0=;
for(int i=;i<=sshu;i++)
{
if(chudu[i]==)chudu0++;
if(rudu[i]==)rudu0++;
}
printf("%d\n",rudu0);
if(sshu==)printf("0\n");
else printf("%d\n",max(chudu0,rudu0));
return ;
}