POJ 1094 -- Sorting It All Out (topological sorting)


POJ 1094 -- Sorting It All Out (topological sorting)
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.
http://www.cnblogs.com/Jason-Damon/archive/2012/04/28/2474436.html
题意:给你一些大写字母间的大小排序关系,判断以下3中情况:1 能唯一确定它们的排列顺序,2 所给关系是矛盾的,3 到最后也不能确定它们之间的关系。
1,不存在拓扑排序,就是表明这些表达式存在矛盾
    2,如果存在唯一的拓扑排序,就可以输出结果
    3,如果不存在唯一的排序,即存在入度相同的点,此时表示不能确定排序关系或者存在结果矛盾(所以在不能确定排序的时候,还要判断是不是存在环,从而确定是不是存在拓扑排序)
题目样例的三种输出分别是:
1. 在第x个关系中可以唯一的确定排序,并输出。
2. 在第x个关系中发现了有回环(Inconsisitency矛盾)
3.全部关系都没有发现上面两种情况,输出第3种.
那么对于给定的m个关系,一个个的读进去,每读进去一次就要进行一次拓扑排序,如果发现情况1和情况2,那么就不用再考虑后面的那些关系了,但是还要继续读完后面的关系(但不处理)。如果读完了所有关系,还没有出现情况1和情况2,那么就输出情况3.
拓扑排序有两种方法,一种是算法导论上的,一种是用贪心的思想,这题用贪心的思想做更好。
贪心的做法:
1. 找到所有入度为0的点, 加入队列Q
2.取出队列Q的一个点,把以这个点为起点,所有它的终点的入度都减1. 如果这个过程中发现经过减1后入度变为0的,把这个点加入队列Q。
3.重复步骤2,直到Q为空。
这个过程中,如果同时有多个点的入度为0,说明不能唯一确定关系。
如果结束之后,所得到的经过排序的点少于点的总数,那么说明有回环。
题目还需要注意的一点:如果边(u,v)之前已经输入过了,那么之后这条边都不再加入。
const int N = 105; 
int n,m,in[N],temp[N],Sort[N],t,pos, num; 
char X, O, Y; 
vector<int>G[N]; 
queue<int>q; 
void init(){ 
    memset(in, 0, sizeof(in)); 
    for(int i=0; i<=n; ++i){ 
        G[i].clear(); 
    
inline bool find(int u,int v){ 
    for(int i=0; i<G[u].size(); ++i) 
        if(G[u][i]==v)return true
    return false
   
int topoSort(){ 
    while(!q.empty())q.pop(); 
    for(int i=0; i<n; ++i)if(in[i]==0){ 
            q.push(i); 
    
    pos=0; 
    bool unSure=false
    while(!q.empty()){ 
        if(q.size()>1) unSure=true
        int t=q.front(); 
        q.pop(); 
        Sort[pos++]=t; 
        for(int i=0; i<G[t].size(); ++i){ 
            if(--in[G[t][i]]==0) 
                q.push(G[t][i]); 
        
    
    if(pos<n) return 1; 
    if(unSure)  return 2; 
    return 3; 
int main(){ 
    int x,y,i,flag,ok,stop; 
    while(~scanf("%d%d%*c",&n,&m)){ 
        if(!n||!m)break
        init(); 
        flag=2; 
        ok=false
        for(i=1; i<=m; ++i){ 
            scanf("%c%c%c%*c", &X,&O,&Y); 
            if(ok) continue; // 如果已经判断了有回环或者可唯一排序,不处理但是要继续读 
            x=X-'A', y=Y-'A'
            if(O=='<'&&!find(y,x)){ 
                    G[y].push_back(x); 
                    ++in[x]; 
            
            else if(O=='>'&&!find(x,y)){ 
                    G[x].push_back(y); 
                    ++in[y]; 
            
            // 拷贝一个副本,等下用来还原in数组 
            memcpy(temp, in, sizeof(in));  
            flag=topoSort(); 
            memcpy(in, temp, sizeof(temp)); 
            if(flag!=2){ 
                stop=i; 
                ok=true
            
        
        if(flag==3){ 
            printf("Sorted sequence determined after %d relations: ", stop); 
            for(int i=pos-1; i>=0; --i) 
                printf("%c",Sort[i]+'A'); 
            printf(".n"); 
        
        else if(flag==1){ 
            printf("Inconsistency found after %d relations.n",stop); 
        
        else
            printf("Sorted sequence cannot be determined.n"); 
        
    
    return 0; 
}

bool adj[MAXN][MAXN];
int in_degree[MAXN];
char str[MAXN];
int n,m;

int topo_sort()
{
    int i,j,k;
    bool flag=true;
    memset(in_degree,0,sizeof(in_degree));
    memset(str,'\0',sizeof(str));
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
            if(adj[i][j])
                in_degree[j]++; //入度加一
    }
    for(i=1; i<=n; i++)  //每次产生一个字符
    {
        k=0;
        for(j=1; j<=n; j++)
        {
            if(in_degree[j]==0)
            {
                if(k==0) k=j;
                else flag=false;  //还有入度为零的节点
            }
        }
        if(k==0) return 0; //没有入度为零的节点,即存在环
        in_degree[k]=-1;
        str[i-1]=k+'A'-1;
        for(j=1; j<=n; j++)  //k指向的节点入度都减一,即去掉A及它相关的边
        {
            if(adj[k][j])
                in_degree[j]--;
        }
    }
    if(flag) return 1;  //没有入度为零的点,完成排序
    else return 2;     //排序没有完成
}

int main()
{
    int i,a,b,result;
    char s[4];
    freopen("acm.txt","r",stdin);
    while(scanf("%d%d",&n,&m),m+n)
    {
        memset(adj,false,sizeof(adj));
        bool h=false;
        for(i=1; i<=m; i++)
        {
            scanf("%s",s);
            a=s[0]-'A'+1; b=s[2]-'A'+1;
            adj[a][b]=true;
            if(h) continue;   //必须有,因为还要继续把剩下的数据都读完
                        result=topo_sort();
            if(result==1)
            {
                printf("Sorted sequence determined after %d relations: %s.\n",i,str);
                h=true;
            }
            if(result==0)
            {
                printf("Inconsistency found after %d relations.\n",i);   //有换存在
                h=true;
            }
        }
        if(!h) printf("Sorted sequence cannot be determined.\n");
    }
    return 0;
}
Read full article from 1094 -- Sorting It All Out

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts