T9的空间

You will never walk alone!
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  69 随笔 :: 0 文章 :: 28 评论 :: 0 Trackbacks
POJ 1094 Topological_Sort（拓扑排序）
Source Code

Problem: 1094  User: Torres 
Memory: 224K  Time: 32MS 
Language: C++  Result: Accepted 

Source Code 
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

#define N 30

vector<vector<int> > G(N);
int re[N];

int Top_sort(vector<vector<int> >G,int n,int *de)
{
    //out<<"www"<<endl;
    int i,j,k;
    memset(re,0,sizeof(re));
    int cnt=0;
    int flag1=0;
    for(i=0;i<n;i++)
    {
        int flag=0;
        for(j=0;j<n;j++)
        {
            if(de[j]==0)  
            {
                flag=1;
                for(k=j+1;!flag1&&k<n;k++)
                    if(de[k]==0)
                    {
                        flag1=1;
                        break;
                    }
                    //说明有两个可供选择的点那么就会产生不同的排列
                re[cnt++]=j;
                de[j]=-1;
                int len=G[j].size();
                for(k=0;k<len;k++)
                    if(de[G[j][k]]>0) de[G[j][k]]--;
                break;
            }
        }
        if(!flag) return 1;//矛盾
    }
    if(flag1) return -1;//不确定
    return 0;//正常
}

int main()
{
    int n,m,i;
    char s[4];
    //freopen("in.txt","r",stdin);
    while(scanf("%d%d",&n,&m))
    {
        if(n==0&&m==0) break;
        int de[N]={0},d[N];
        int t;
        for(t=1;t<=m;t++)
        {
            scanf("%s",s);
            G[s[0]-'A'].push_back(s[2]-'A');
            de[s[2]-'A']++;
        //    for(i=0;i<n;i++)
        //        cout<<de[i]<<endl;
            memcpy(d,de,sizeof(de));
            int ans=Top_sort(G,n,d);
            if(ans==1)
            {
                printf("Inconsistency found after %d relations.\n",t);
                while(t<m) scanf("%s",s),t++;
            }
            else if(ans==0)
            {
                printf("Sorted sequence determined after %d relations: ",t);
                for(i=0;i<n;i++)
                    printf("%c",re[i]+'A');
                printf(".\n");
                while(t<m) scanf("%s",s),t++;
            }
            else if(t==m&&ans==-1)
                printf("Sorted sequence cannot be determined.\n");

        }
        for(i=0;i<n;i++)
            G[i].clear();
    }
    return 0;
}
posted on 2008-10-20 22:18 Torres 阅读(321) 评论(0)  编辑 收藏 引用 所属分类: Data Structures

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理