本文主要是介绍poj-1236-Network of Schools-强联通分量，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意：一些学校连成了网络， 在学校之间存在某个协议:每个学校都维护一张传送表，表明他们要负责将收到的软件传送到表中的所有学校。如果A在B的表中，那么B不一定在A的表中。
现在的任务就是，给出所有学校及他们维护的表，问1、如果所有学校都要被传送到，那么需要几份软件备份；2、如果只用一份软件备份，那么需要添加几条边？
做法：
tarjan算法求缩点。
如果入度为0的点的个数为ans1，出度为0的点的个数为ans2。
如果所有的学校都要被传送到，那么把软件放在入度为0的点上即可。即答案为ans1。
如果只有一份软件，那么就需要把原图连接成一个强联通图。那么从出度为0的点往入度为0的点上连边。只要所有的点都被连过，那么就会成为一个强联通图。
即答案为max(ans1,ans2);
#include <iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
using namespace std;
#define maxm 110*110
#define maxn 110
#define eps 0.000001
#define zero(x) ((fabs(x)<eps?0:x))
#define INF 99999999
struct gra
{struct list{int u,v,next;} edge[maxm];int head[maxn];int vis[maxn];int num;int n;int id[maxn];int od[maxn];int shuyu[maxn];int nums;int dnf[maxn],low[maxn],times,instack[maxn];stack<int>qq;void init(){memset(head,-1,sizeof(head));memset(vis,0,sizeof(vis));memset(shuyu,0,sizeof(shuyu));memset(dnf,0,sizeof(dnf));memset(low,0,sizeof(low));memset(instack,0,sizeof(instack));while(!qq.empty())qq.pop();num=0;nums=1;times=1;}void add(int u,int v){edge[num].u=u;edge[num].v=v;edge[num].next=head[u];head[u]=num++;}void tarjan(int x){dnf[x]=low[x]=times++;instack[x]=1;qq.push(x);for(int i=head[x]; i!=-1; i=edge[i].next){int y=edge[i].v;if(!dnf[y]){tarjan(y);low[x]=min(low[x],low[y]);}else if(instack[y]){low[x]=min(low[x],dnf[y]);}}if(low[x]==dnf[x]){int y=-1;while(x!=y){y=qq.top();shuyu[y]=nums;qq.pop();instack[y]=0;}nums++;}}void start(){int i,j;for(i=1; i<=n; i++){// cout<<i<<endl;if(!dnf[i])tarjan(i);}for(i=1;i<=n;i++){for(j=head[i];j!=-1;j=edge[j].next){int u=edge[j].u;int v=edge[j].v;if(shuyu[u]==shuyu[v])continue;id[shuyu[v]]++;od[shuyu[u]]++;}}}
}G;
int main()
{int n,i,x;while(~scanf("%d",&n)){G.init();G.n=n;for(i=1; i<=n; i++){while(scanf("%d",&x)&&x){G.add(i,x);}}G.start();if(G.nums==2){cout<<"1"<<endl;cout<<"0"<<endl;continue;}int nin,nout;nin=nout=0;for(i=1;i<G.nums;i++){if(G.id[i]==0)nin++;if(G.od[i]==0)nout++;}cout<<nin<<endl;cout<<max(nin,nout)<<endl;}return 0;
}
这篇关于poj-1236-Network of Schools-强联通分量的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
