现在的位置: 首页 > 综合 > 正文

POJ2367【水拓扑】

2013年09月12日 ⁄ 综合 ⁄ 共 679字 ⁄ 字号 评论关闭
int ans[200];
int fa[200];
int n;
void toposort()
{
    int cnt=0;
    memset(in,0,sizeof(in));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if(adj[i][j]==1)
                in[j]++;
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if(in[j]==0)
               {
                  ans[cnt++]=j;
                  in[j]=-1;
                  for(int qq=1;qq<=n;qq++)
                   if(adj[j][qq]>0)
                    adj[j][qq]=0,in[qq]--;//?
                    break;
               }
        }
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
       int d,cnt;
       memset(adj,0,sizeof(adj));
       memset(ans,0,sizeof(ans));
       for(int i=1;i<=n;i++)
       {
           while(scanf("%d",&d)&&d)
             adj[i][d]=1;
       }
       /*for(int i=1;i<=n;i++)
          for(int j=1;j<=n;j++)
              if(adj[i][j]==1)
                 printf("%d %d\n",i,j);*/
       toposort();
       for(int i=0;i<n;i++)
         printf("%d ",ans[i]);
       printf("\n");
    }
    return 0;
}

就照着自己模仿的题意写了写结果老WA,后来才发现是题意猜错了,然后一改就AC。
这个没要求输出顺序。
另外while(scanf("%d",&a)&&a)。。。

抱歉!评论已关闭.