POJ 1094 Sorting It All Out

題意：
    給定N表示有N個點，M表示底下有M行關係式，然後一行一行讀取關係式：

• 如果在第i行發現已經能明確將所有點排出順序(也就是只有一種答案)，輸出Sorted sequence determined after i relations: ...(順序)
• 如果在第i行發現和之前的關係式有衝突(形成一個環，例如A>B>C>A)，則輸出Inconsistency found after i relations.
• 如果讀取到最後關係都沒有衝突但也找不到唯一答案，則輸出Sorted sequence cannot be determined.

想法：

    每次讀取關係式的時候就檢查是否有衝突(形成一個環)，如果沒有再去找topological sort，topological sort這function裡面要判斷是否為唯一解，因此只能選一條路徑往下遞迴，最後判斷答案優先順序為1.先看有沒有衝突2.看有沒有解，再依題目敘述輸出即可，詳細看底下code。

	#include <cstdio>
	#include <vector>
	using namespace std;
	vector<int> toNxt[30]; // toNxt[i]裡面存i這個點在哪些點前面
	int deg[30]; // deg[i]表示在i前面有多少個點
	vector<int> Ans;
	void Initial(int N)
	{
	Ans.clear();
	for (int i = 0; i < N; ++i) {
	toNxt[i].clear();
	deg[i] = -1; // 用-1表示該點還沒出現過
	}
	}
	bool Trace(int a, int b) //確認a這個點是否在b這個點前面
	{
	if (a == b) return true;
	for (int i = 0; i < toNxt[a].size(); ++i) {
	if (Trace(toNxt[a][i], b)) return true;
	}
	return false;
	}
	void topological_sort(int N)
	{
	int Count = 0, a;
	for (int i = 0; i < N; ++i)
	if (deg[i] == 0){
	a = i;
	Count++;
	}
	if (Count != 1) return; // 要確定這個lopological sort只有唯一解
	Ans.push_back(a);
	--deg[a];
	for (int i = 0; i < toNxt[a].size(); ++i)
	--deg[toNxt[a][i]];
	topological_sort(N);
	++deg[a];
	for (int i = 0; i < toNxt[a].size(); ++i)
	++deg[toNxt[a][i]];
	}
	int main()
	{
	int N, M;
	char str[10];
	while (scanf("%d %d", &N, &M) && (N || M)) {
	Initial(N);
	int Inconsistency = 0; //記錄關係式發生衝突的行數
	int hasAns = 0; //記錄這Case是否有解
	for (int i = 0; i < M; ++i) {
	scanf("%s", str);
	int a = str[0]-'A';
	int b = str[2]-'A';
	//如果Inconsistency還沒記錄過且b在a的前面
	if (!Inconsistency && Trace(b, a)) Inconsistency = i + 1;
	else if(!Inconsistency){ // 如果沒有發生衝突
	toNxt[a].push_back(b);
	if (deg[a] == -1) deg[a] = 0;
	if (deg[b] == -1) deg[b] = 0;
	++deg[b];
	Ans.clear();
	if (!hasAns) {
	topological_sort(N);
	if (Ans.size() == N) hasAns = i + 1;
	}
	}
	}
	if (hasAns) {
	printf("Sorted sequence determined after %d relations: ", hasAns);
	for (int i = 0; i < N; ++i)
	printf("%c", (char)Ans[i] + 'A');
	printf(".\n");
	}
	else {
	if (Inconsistency) printf("Inconsistency found after %d relations.\n", Inconsistency);
	else printf("Sorted sequence cannot be determined.\n");
	}
	}
	}

view raw [POJ] 1094 Sorting It All Out.cpp hosted with ❤ by GitHub