T9的空间

You will never walk alone!

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  69 随笔 :: 0 文章 :: 28 评论 :: 0 Trackbacks
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==0break;
        
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 阅读(305) 评论(0)  编辑 收藏 引用 所属分类: Data Structures

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