注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

POJ2186Popular Cows题解  

2014-03-14 21:42:06|  分类: POJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
                                                                        受欢迎的奶牛
                                                BY   LGS
题目大意:有N个奶牛,M对关系,一对关系A,B表示A觉得B受欢迎,求大家都认为受欢迎的奶牛的个数,关系具有传递性。自己不会认为自己受欢迎。

题解:此题可以转换如下:有一个有向图,求所有点都可以到它的这个“它”个数。如果N的个数小于=100,那么直接暴力(FOLYED)就可以了。而题目里有10000个点,50000条边,那么只能通过缩点(缩强连通分量为1个点)以后形成新图进行判断。新图中如果某个点的出度为0且只有这么一个,那这个点一定是受大家欢迎的,统计这个点里实际的点数即可。有多个,那么就是无解。由于二维邻接表会萎,所以只能用边表(详见推荐阅读),而我用的缩点法是Kosaraju(详见推荐阅读),这个时间复杂度是(N+M)的。并且这个算法需要反向边,所以要2张边表,即空间复杂度为2*(N+M)。

总结:题目难度适中,缩点法。
代码:
#include<cstdio>
#include<cstring>
using namespace std;
int i,j,n,m,fa[10001],fa2[10001],newline[10001],color,ran[10001],tot,x,y,ans
,flag,sum,tot2;
bool l[10001],chu[10001];
struct node{
int end,next;
}g[50001],gg[50001];
void add(int x,int y)
 {
 tot++;
 g[tot].end=y;
 g[tot].next=fa[x];
 fa[x]=tot;
 }
void add2(int x,int y)
 {
 tot2++;
 gg[tot2].end=y;gg[tot2].next=fa2[x];
 fa2[x]=tot2;
 }
void dfs(int w)
 {
 l[w]=true;
 int i=fa[w];
 while (i)
         {
         if (!l[g[i].end]) dfs(g[i].end);
         i=g[i].next;
         }  
 newline[++tot]=w;
 }
void dfs2(int w)
 {
 ran[w]=color;l[w]=true;
 int i=fa2[w];
 while (i){ 
          if (!l[gg[i].end]) dfs2(gg[i].end);
          i=gg[i].next;
          }   
 }
void Kosaraju()
 {
 tot=0;
 for (int i=1;i<=n;i++)
          if (!l[i]) dfs(i);
 memset(l,false,sizeof(l));color=0;
 for (int i=n;i>=1;i--)
         if (!l[newline[i]]) {
                    color++;
                    dfs2(newline[i]);
                             }
 }
int main()
{
 scanf("%d%d",&n,&m);tot=0;tot2=0;
 for (i=1;i<=m;i++)
  {
  scanf("%d%d",&x,&y);
  add(x,y);
  add2(y,x);
  }
Kosaraju(); 
for (i=1;i<=n;i++)if (!chu[ran[i]])
                       {
               int k=fa[i];
               while (k){
               if (ran[g[k].end]!=ran[i]){
                                         chu[ran[i]]=true;
                                         break;
                                          }
                         k=g[k].next;
                        }
                       }
ans=0;flag=0;sum=0;
for (i=1;i<=color;i++)if (!chu[i]) {ans++;flag=i;}

if (ans==1){
            for (i=1;i<=n;i++)if (ran[i]==flag) sum++;
            printf("%d",sum);
           }
           else printf("0");
//for(;;);
return 0;
}
  评论这张
 
阅读(21)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018