Coder Space

PKU 1094 Sorting It All Out--- 拓扑排序

题意：根据给出的<关系，确定字母的排序序列。
            1. 若<关系存在茅盾(图有环)，答案为“Inconsistency”，
            2. 若序列不唯一，答案为“cannot be determined”，
            3. 否则为“determined”。

注意：必须每输入一个<关系，判断一次，当前关系可得到唯一序列时，则为“determined”，即使后面的关系可以造成茅盾。

解法：拓扑排序，每输入一条关系，执行一次拓扑排序，注意判断是否存在环。

  1#include<iostream>
  2#include<queue>
  3
  4using namespace std;
  5
  6const int maxN = 27;
  7
  8bool G[maxN][maxN];
  9
 10int TopSort(int n,int sq[])        //sq记录有序序列
 11{
 12    queue<int> q;
 13
 14    int cnt = 0;
 15    bool Found = true;             //序列是否唯一
 16
 17    int degree[maxN];              //入度表
 18    bool visited[maxN];
 19
 20    for(int i=1; i<=n; i++)
 21    {
 22        visited[i] = false;
 23        degree[i] = 0;
 24
 25        for(int j=1; j<=n; j++)
 26        {
 27            if(G[j][i])
 28            {
 29                degree[i]++;          //求入度
 30            }
 31        }
 32        if(degree[i] == 0)            //入度为0的点压进队列
 33        {
 34            q.push(i);
 35        }
 36    }
 37
 38    while(!q.empty())
 39    {
 40        if(q.size() > 1)              //若存在多个0入度点，则序列不唯一
 41        {
 42            Found = false;
 43        }
 44        int cur = q.front();
 45        sq[++cnt] = cur;
 46        q.pop();
 47
 48        for(int j=1; j<=n; j++)
 49        {
 50            if(G[cur][j])             //删除边
 51            {
 52                degree[j]--;
 53                if(degree[j] == 0)
 54                {
 55                    q.push(j);
 56                }
 57            }
 58        }
 59    }
 60
 61    if(cnt != n)                     //如果没有遍历所有顶点，则存在环
 62    {
 63        return 1;                    //存在环，返回1
 64    }
 65    else if(Found)
 66    {
 67        return 2;                    //确定唯一序列，返回2
 68    }
 69    return 0;                        //序列不确定，返回0
 70}
 71
 72int main()
 73{
 74    int n,m;
 75    char a,b,t;
 76
 77    int resCode,cnt;            //resCode为结果编码,cnt为得到结果所用的关系条数
 78    int sq[maxN];
 79
 80    int i,j;
 81
 82    cin>>n>>m;
 83
 84    while(!(n==0 && m==0))
 85    {
 86        for(i=1; i<=n; i++)
 87        {
 88            for(j=1; j<=n; j++)
 89            {
 90                G[i][j] = false;
 91            }
 92        }
 93        resCode = 0;
 94        cnt = 0;
 95
 96        for(i=1; i<=m; i++)
 97        {
 98            cin>>a>>t>>b;
 99            if(resCode == 0)
100            {
101                G[a-'A'+1][b-'A'+1] = true;
102
103                resCode = TopSort(n,sq);
104                if(resCode != 0)
105                {
106                    cnt = i;
107                }
108            }
109        }
110
111        switch(resCode)
112        {
113        case 0:
114            cout<<"Sorted sequence cannot be determined."<<endl;
115            break;
116
117        case 1:
118            cout<<"Inconsistency found after "<<cnt<<" relations."<<endl;
119            break;
120
121        case 2:
122            cout<<"Sorted sequence determined after "<<cnt<<" relations: ";
123            for(i=1; i<=n; i++)
124            {
125                cout<<char(sq[i] - 1 + 'A');
126            }
127            cout<<"."<<endl;
128            break;
129        }
130
131        cin>>n>>m;
132    }
133    return 0;
134}

posted on 2010-05-15 01:31 David Liu 阅读(113) 评论(0)  编辑 收藏 引用 所属分类: 图论


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


My Links

Blog Stats

常用链接

留言簿

文章分类

文章档案

搜索

最新评论