POJ 1094 Sorting It All Out

Sorting It All Out

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 24591		Accepted: 8517

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

可以确定关系的 > 矛盾的 > 多解的所以如果是多解的还要进行判环

  1  #include <iostream>
  2  #include <cstdio>
  3  #include <cstring>
  4  #include <set>
  5  #include <vector>
  6 
  7  using namespace std;
  8 
  9  int n,m,g[30][30],id1[30],id2[30];
 10  bool vis[30],VK;
 11  int topo(int nt,int id[30])
 12  {
 13      vector<char> v;
 14      while(v.size()!=n)
 15      {
 16          int pos=-1,cnt=0;
 17          for(int i=0;i<n;i++)
 18              if(id[i]==0)
 19              {
 20                  if(pos==-1) pos=i;
 21                  cnt++;
 22              }
 23          if(cnt>1) return 0;
 24          else if(cnt==1)
 25          {
 26              v.push_back(pos+'A');
 27              for(int j=0;j<n;j++)
 28              {
 29                  if(g[pos][j])
 30                  {
 31                      id[j]--;
 32                  }
 33              }
 34              id[pos]=-1;
 35          }
 36          if(pos==-1)
 37          {
 38              printf("Inconsistency found after %d relations.
",nt);
 39              return -1;
 40          }
 41      }
 42     printf("Sorted sequence determined after %d relations: ",nt);
 43     for(int i=0;i<n;i++)
 44         printf("%c",v[i]);
 45     printf(".
");
 46     return 1;
 47  }
 48 
 49  bool floyd()
 50  {
 51      int mark[30][30];
 52      memcpy(mark,g,sizeof(mark));
 53      for(int k=0;k<n;k++)
 54         for(int i=0;i<n;i++)
 55            for(int j=0;j<n;j++)
 56      {
 57          if(g[i][k]&&g[k][j])
 58             mark[i][j]=1;
 59      }
 60      for(int i=0;i<n;i++)
 61      {
 62          for(int j=i+1;j<n;j++)
 63             if(mark[i][j]&&mark[j][i])
 64             return true;
 65      }
 66      return false;
 67  }
 68 
 69  int main()
 70  {
 71      while(scanf("%d%d",&n,&m)!=EOF)
 72      {
 73          if(n==0&&m==0) break;
 74          getchar();
 75          set<char> s;
 76          bool cont=false;int num=0;
 77          memset(g,0,sizeof(g));
 78          memset(id1,0,sizeof(id1));
 79          for(int i=1;i<=m;i++)
 80          {
 81              char a[2],b[2];
 82              scanf("%c<%c",&a[0],&b[0]);
 83              getchar();
 84             if(cont) continue;
 85              g[a[0]-'A'][b[0]-'A']=1;
 86              id1[b[0]-'A']++;
 87              memcpy(id2,id1,sizeof(id1));
 88              int sin=topo(i,id2);
 89              ///youjie
 90              if(sin==1||sin==-1) cont=true;
 91              if(sin==0)
 92              {
 93                  if( floyd() )
 94                  {
 95                      printf("Inconsistency found after %d relations.
",i);
 96                      cont=true;
 97                  }
 98              }
 99          }
100          if(cont==false)
101             printf("Sorted sequence cannot be determined.
");
102      }
103      return 0;
104  }