POJ 1236 Network of Schools(强连通分量） - c++编程基础

TOP

POJ 1236 Network of Schools(强连通分量）

2015-07-20 17:49:18 来源: 作者: 【大中小】浏览:3次

题目地址：POJ 1236

这个题的大意是求最少往多少点发送消息可以使任意一个点都能收到消息和最少增加多少条边可以使图为连通图。对于第一个问题，可以求入度为0的强连通块的块数，因为只有入度为0的强连通块是无法从外界接受信息的，而只要有一个入度的话，那整个连通块就都可以接收到信息。第二个问题则是求入度为0的强连通块与出度为0的强连通块的个数的最大值。

代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              using namespace std; int head[200], cnt, index, top, ans, cntin, cntout, in[200], out[200]; int dfn[200], belong[200], instack[200], stak[200], low[200]; struct node { int u, v, next; } edge[100000]; void add(int u, int v) { edge[cnt].v=v; edge[cnt].next=head[u]; head[u]=cnt++; } void init() { memset(head,-1,sizeof(head)); cnt=0; memset(instack,0,sizeof(instack)); memset(dfn,0,sizeof(dfn)); top=index=ans=0; cntin=cntout=0; memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); } void tarjan(int u) { dfn[u]=low[u]=++index; instack[u]=1; stak[++top]=u; for(int i=head[u]; i!=-1; i=edge[i].next) { int v=edge[i].v; if(!dfn[v]) { tarjan(v); low[u]=min(low[v],low[u]); } else if(instack[v]) low[u]=min(low[u],dfn[v]); } if(dfn[u]==low[u]) { ans++; while(1) { int v=stak[top--]; belong[v]=ans; instack[v]=0; if(u==v) break; } } } int main() { int n, i, j, a; scanf("%d",&n); init(); for(i=1; i<=n; i++) { while(scanf("%d",&a)&&a) { add(i,a); } } for(i=1; i<=n; i++) { if(!dfn[i]) tarjan(i); } if(ans==1) printf("1\n0\n"); else { for(i=1; i<=n; i++) { for(j=head[i]; j!=-1; j=edge[j].next) { int v=edge[j].v; if(belong[i]!=belong[v]) { in[belong[v]]++; out[belong[i]]++; } } } for(i=1; i<=ans; i++) { if(!in[i]) cntin++; if(!out[i]) cntout++; } printf("%d\n%d\n",cntin,max(cntin,cntout)); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：CodeForces 46DParking Lot线段树	下一篇：HDU 4339 Query

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: