T9的空间

You will never walk alone!

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  69 随笔 :: 0 文章 :: 28 评论 :: 0 Trackbacks
//基于AOV(activity on vertex)网络的拓扑排序

#include
<iostream>
#include
<string>
#include
<algorithm>
#include
<vector>
using namespace std;

#define VN 20
vector
<int> p[VN]; 
int de[VN];

int main()
{
    
int i,j,s,e;
    
int n;
    
int re[VN];
    memset(de,
0,sizeof(de));
    freopen(
"in.txt","r",stdin);
    scanf(
"%d",&n);
    
while(scanf("%d%d",&s,&e))
    
{
        
if(s==0&&e==0break;
        p[s].push_back(e);
        de[e]
++;
    }

    
int k=0;
    
int flag;
    
for(i=1;i<=n;i++)
    
{
        flag
=0;
        
for(j=1;j<=n;j++)
            
if(de[j]==0
            
{
                re[k
++]=j;
                
int len=p[j].size();
                
for(int t=0;t<len;t++)
                    de[p[j][t]]
--;
                de[j]
=-1;
                flag
=1;
                
break;
            }

        
if(!flag) break;
    }

    
if(k<n) printf("Can't do it\n");
    
else
    
{
        
for(i=0;i<n;i++)
            printf(
"%d ",re[i]);
        printf(
"\n");
    }

    
return 0;
}

测试结果:
8
2 1
3 2
2 4
5 4
7 8
1 8
8 3
3 6
4 8
4 6
0 0
Can't do it

8
2 1
2 3
2 4
5 4
7 8
1 8
3 8
3 6
4 8
4 6
0 0
2 1 3 5 4 6 7 8

posted on 2008-10-19 10:45 Torres 阅读(215) 评论(0)  编辑 收藏 引用 所属分类: Data Structures

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理