poj 1206 Network of Schools

本文主要是介绍poj 1206 Network of Schools，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一问，求出缩点后入度为零的点数，二问，缩点后分别求出入度为零和出度为零,取比较大的，当然，如果是强连通图，输出0就好了.
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
int edge[110][110];
int low[110],dfn[110],vis[110],num[110],index[110],in[110],out[100];
int stack[400];
int n,ins,ous,fpt,ntp,top,a;
void tarjan(int i)
{
int u,w;
vis[i]=1;
stack[top++]=i; 
low[i]=dfn[i]=ntp++;
for(int j=1;j<=edge[i][0];j++)
{
w=edge[i][j];
if(dfn[w]==-1)
{
tarjan(w);
low[i]=min(low[i],low[w]);
}
else if(vis[w]) low[i]=min(low[i],dfn[w]);
}
if(low[i]==dfn[i])
{
fpt++;
do{ u=stack[--top]; vis[u]=0; index[u]=fpt;} while(u!=i);
}
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
ins=0;ous=0;fpt=0;ntp=0;top=0;
memset(dfn,-1,sizeof(dfn));
memset(vis,0,sizeof(vis));
memset(in,0,sizeof(in));
memset(out,0,sizeof(out));
// memset(index,0,sizeof(index));
memset(edge,0,sizeof(edge));
for(int i=1;i<=n;i++)
{
while(scanf("%d",&a)&&a)
{
edge[i][++edge[i][0]]=a;
}
}
for(int i=1;i<=n;i++)
{
if(dfn[i]==-1)  tarjan(i);
}
if(fpt==1) { printf("%d\n%d\n",1,0);  continue;}
for(int i=1;i<=n;i++)
for(int j=1;j<=edge[i][0];j++)
{
if(index[i]!=index[edge[i][j]]) {out[index[i]]++;  in[index[edge[i][j]]]++;}
}
for(int i=1;i<=fpt;i++)
{
if(in[i]==0)  ins++;
if(out[i]==0) ous++;
}
printf("%d\n",ins);
if(ins>ous)  printf("%d\n",ins);
else printf("%d\n",ous);       
}
return 0;
}

这篇关于poj 1206 Network of Schools的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---