巢穴

about:blank

P1094

拓扑排序..
这个真是WA了n多次..orz..
总之就是有很多细节..因为结果的可能性太多..而样例实在是只给了太少的可能性- -..

#include <iostream>
#include <queue>
#include <string>
using namespace std;
int n,m;
const int MAXN=27;
bool edge[MAXN][MAXN];
int d[MAXN];
int state;


void jude(int ix)
{
     state=0;
     string str="";
     int count=0;
     queue<int> q;
     int u[MAXN];
     for (int i=1;i<=n;i++)
     {   
          u[i]=d[i];
        //  cout<<u[i]<<endl;
          if (0==d[i]) q.push(i);
     }
     if (q.size()>1) {state=3;}
     while(q.size()>0)
     {
      int v=q.front();
      int c_ount=0;
      for (int i=1;i<=n;i++)
          if (edge[i][v])
          {
           u[i]--;
           if (0==u[i]) {c_ount++;q.push(i);}
          }
      if (c_ount>1) {state=3;}
      q.pop();count++;str=char(v+64)+str;
     }
    // cout<<count<<" "<<n<<endl;
     if (count<n)
     {
      cout<<"Inconsistency found after "<<ix<<" relations."<<endl;
      state=2;return;
     }
     if (state==3) return;
     cout<<"Sorted sequence determined after "<<ix<<" relations: ";
     cout<<str<<"."<<endl;
     state=1;return;
     
}
int main()
{
    while(1)
    {           
     memset(edge,0,sizeof(edge));
     memset(d,0,sizeof(d));
     state=0;  
     cin>>n>>m;     
     if (0==n&&0==m) break;
     char str[3];
     for (int i=1;i<=m;i++)
     {
     
         cin>>str;
         if (state==1) continue;
         if (state==2) continue;
         int x=int(str[0])-64;
         int y=int(str[2])-64;
         if (edge[x][y]) continue;
         d[x]=d[x]+1;
         edge[x][y]=true;
         jude(i);

     }
     if (state==3) cout<<"Sorted sequence cannot be determined."<<endl;
     
    }
    return 0;
}

posted on 2009-10-07 18:25 Vincent 阅读(131) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法


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