首页 > 代码库 > POJ 1236 Network of Schools 连通图缩点
POJ 1236 Network of Schools 连通图缩点
题目大意:有向图连通图,第一问求至少需要多少个软件才能传输到所有学校,第二问求至少需要增加多少条路使其成为强连通图
题目思路:利用Tarjan算法经行缩点,第一问就是求缩点后入度为0的点的个数(特殊情况,当缩点后仅剩一个点是输出0),第二问就是求缩点后max(入度为0的点的个数,出度为0的点的个数)。
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<math.h> #include<iostream> #include<queue> #include<algorithm> #define INF 0x3f3f3f3f #define MAXSIZE 105 #define LL long long using namespace std; int Stuck[MAXSIZE],vis[MAXSIZE],dfn[MAXSIZE],low[MAXSIZE],belong[MAXSIZE],in[MAXSIZE],out[MAXSIZE],block,k,Time,e,n,Map[MAXSIZE][MAXSIZE]; void Tarjan(int u) { dfn[u]=low[u]=++Time;//时间戳 Stuck[++k]=u; vis[u]=1; for(int i=1;i<=n;i++) { if(!Map[u][i]) continue; if(!dfn[i]) { Tarjan(i); low[u]=min(low[u],low[i]); } else if(vis[i]) { low[u]=min(low[u],dfn[i]); } } if(low[u]==dfn[u]) { int temp; do{ temp=Stuck[k--]; belong[temp]=block;//记录该点属于哪个“块” vis[temp]=0; }while(u!=temp); block++;//更新“块”数 } } int main() { int a; while(scanf("%d",&n)!=EOF) { memset(Map,0,sizeof(Map)); memset(vis,0,sizeof(vis)); memset(belong,0,sizeof(belong)); memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); memset(low,0,sizeof(low)); memset(dfn,0,sizeof(dfn)); Time=0; block=1; k=0; for(int i=1;i<=n;i++) { while(scanf("%d",&a),a) { Map[i][a]=1; } } for(int i=1;i<=n;i++) { if(!dfn[i]) { Tarjan(i); } } for(int i=1;i<=n;i++)//缩点过程 { for(int j=1;j<=n;j++) { if(!Map[i][j]) continue; if(belong[i]!=belong[j])//i,j分别属于不同的“块”,且i到j有路径,那么i所在“块”的出度加一,j所在“块”的入度加一 { out[belong[i]]++; in[belong[j]]++; } } } int sum_in=0; int sum_out=0; for(int i=1;i<block;i++) { if(!in[i]) sum_in++; if(!out[i]) sum_out++; } int ans=max(sum_in,sum_out);//两者最大值即为需新增的路径数 if(block==2) printf("1\n0\n"); else printf("%d\n%d\n",sum_in,ans); } return 0; }
POJ 1236 Network of Schools 连通图缩点
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。