欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POJ1094 Sorting It All Out 拓扑排序 入度(注意优先级)

程序员文章站 2024-03-13 23:22:22
...

POJ1094 Sorting It All Out 拓扑排序 入度(注意优先级)

Sorting It All Out

Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 40917 Accepted: 14342
Description

An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not.

Input

Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n <= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character “<” and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input.

Output

For each problem instance, output consists of one line. This line should be one of the following three:

Sorted sequence determined after xxx relations: yyy…y.
Sorted sequence cannot be determined.
Inconsistency found after xxx relations.

where xxx is the number of relations processed at the time either a sorted sequence is determined or an inconsistency is found, whichever comes first, and yyy…y is the sorted, ascending sequence.
Sample Input

4 6
A<B
A<C
B<C
C<D
B<D
A<B
3 2
A<B
B<A
26 1
A<Z
0 0

Sample Output

Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.
Source

East Central North America 2001

注意优先级的选择

Inconsistency found :出现环后立刻跳出循环。
Sorted sequence cannot be determined :加入所有边后输出。
Sorted sequence determined: 全部排序确定后输出。

代码如下:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <set>
#include <string>
#include <queue>
#include <map>
#include <vector>
#include <cstring>
#include <algorithm>
#include <sstream>
#define INF 10000000
#define MAXN 2e5+9
const long long mod=1e6+3;
using namespace std;
int in[50];
int via[50];
vector<int> vec[50];
void mclear(queue<int> &q)
{
    queue<int> e;
    swap(e,q);
}
void init()
{
    for(int i=0;i<27;i++)
    {
        vec[i].clear();
    }
}
//queue<int> ans;
int main()
{
    int n,m;
    while (scanf("%d%d",&n,&m)==2 && (m||n))
    {
        init();
        int i,j,k;
        int f=0;
        char c[5];
        for(i=1;i<=m;i++)
        {
            //memset(via,0,sizeof(via));
            memset(in,0,sizeof(in));
            scanf("%s",c);
            //cout << c <<endl;
            if(f==1 || f==3) continue;
            vec[c[0]-'A'].push_back(c[2]-'A');
            for(j=0;j<n;j++)
            {
                //cout << j << "   ";
                for(k=0;k<vec[j].size();k++)
                {
                  //  cout << vec[j][k] <<' ';
                    in[vec[j][k]]++;
                }
                //cout << endl;
            }
            for(j=0;j<n;j++)
            {
                //cout << in[j] <<' ';
            }
           // cout << endl;
            int num=n;
            queue<int> q;
            if(f==2) f=0;
            while (num>0)
            {
                int cnt=0;
                for(j=0;j<n;j++)
                {
                    if(in[j]==0) cnt++;
                }
             //   if(i==4) cout << cnt << endl;
                if(cnt==0)
                {
                    f=1;
                    break;
                }
                if(cnt>1)
                {
                    f=2;
                }
                for(j=0;j<n;j++)
                {
                    if(in[j]==0)
                    {
                        num--;
                        q.push(j);
                        in[j]=-1;
                        for(k=0;k<vec[j].size();k++)
                        {
                            in[vec[j][k]]--;
                        }
                        break;
                    }
                }
            }
            if(f!=1 && f!=2) f=3;
            if(f==1)
            {
                cout <<"Inconsistency found after "<< i <<" relations."<<endl;
            }
            if(f==3)
            {
                cout <<"Sorted sequence determined after "<< i <<" relations: ";
                while (!q.empty())
                {
                    cout << (char)(q.front()+'A');
                    q.pop();
                }
                cout << '.'<<endl;
            }
        }
        if(f==2)
        {
            cout << "Sorted sequence cannot be determined."<<endl;
        }
    }
    return 0;
}
相关标签: 拓扑