Floyd判聯通(傳遞閉包)

Floyd傳遞閉包顧名思義就是把判最短路的代碼替換成了判是否連通的代碼，它可以用來判斷圖中兩點是否連通。板子大概是這個樣的：

for(int k=1; k<=n; k++){
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			// 把數值計算替換成邏輯運算——就一行，非常簡便
			e[i][j] = e[i][j] || (e[i][k] && e[k][j]);
		}
	}
}

題目描述

給定 n個變數和 m個不等式。其中 n小於等於 26，變數分別用前 n的大寫英文字母表示。

不等式之間具有傳遞性，即若 A>B 且 B>C，則 A>C。

請從前往後遍歷每對關係，每次遍歷時判斷：

• 如果能夠確定全部關係且無矛盾，則結束迴圈，輸出確定的次序；
• 如果發生矛盾，則結束迴圈，輸出有矛盾；
• 如果迴圈結束時沒有發生上述兩種情況，則輸出無定解。
  輸入格式
  輸入包含多組測試數據。

每組測試數據，第一行包含兩個整數 n和 m。

接下來 m行，每行包含一個不等式，不等式全部為小於關係。

當輸入一行 0 0 時，表示輸入終止。

輸出格式
每組數據輸出一個占一行的結果。

結果可能為下列三種之一：

1. 如果可以確定兩兩之間的關係，則輸出 "Sorted sequence determined after t relations: yyy...y.",其中't'指迭代次數，'yyy...y'是指升序排列的所有變數。
2. 如果有矛盾，則輸出： "Inconsistency found after t relations."，其中't'指迭代次數。
3. 如果沒有矛盾，且不能確定兩兩之間的關係，則輸出 "Sorted sequence cannot be determined."。

那麼我們可以分析題目：題目說要“從前往後遍歷每對關係” 那麼就不是一次性導入所有數據了，而是每輸入一個就計算一遍。

那麼怎麼判斷是否存在矛盾呢？想想看，不就是既有\(A>B\) 又有\(B>A\)嗎。那麼就可以在floyd的同時加入判斷。

for(int k=1; k<=n; k++){
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			e[i][j] = e[i][j] || (e[i][k] && e[k][j]);
			// 註意要i!=j
			// 如果e[i][j]和e[j][i]都聯通肯定存在矛盾
			if(e[i][j] && e[j][i] && i!=j){
				data = 0;
			}
		}
	}
}

那怎麼判斷能否確定兩兩關係呢？那就是在沒有矛盾的前提下，兩兩首尾相連。如果存在兩個點沒有首尾相連的情況，那肯定不行的。我這裡把判斷它的代碼單獨拿了出來放在一個函數里，因為如果在floyd中寫的話它是會變化的，可能在某次迴圈時它不連通，但迴圈幾次後它又聯通了。所以還不如拿出去.

bool check(){
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			if(!e[i][j] && !e[j][i] && i!=j) return 0;
		}
	}
	return 1;
}

可以判斷兩兩關係了，那怎麼列印出次序呢？我在某個大佬那裡受到啟發——觀察矩陣。試想一下，如果\(A<B<C<D\)，那麼A聯通的點有3個，B聯通的點有2個，C聯通的點有…… 也就是這個樣子的:

A[1][n] 0 1 1 1
B[2][n] 0 0 1 1
C[3][n] 0 0 0 1
D[4][n] 0 0 0 0

那麼就只用依次取出“1”最多的列印出來就好。

inline void out(){
	// #define p pair<int, char>
	priority_queue<p, vector<p>, less<p> > q;
	int t;
	for(int i=1; i<=n; i++){
		t = 0;
		for(int j=1; j<=n; j++){
			if(i != j) t += e[i][j];
		}
		q.push( (p){t, i-1+'A'} );
	}
	while(!q.empty()){
		printf("%c",q.top().second);
		q.pop();
	}
	printf(".\n");
}

這道題個人感覺非常nice，他開拓了我們的新思路：觀察矩陣(找規律)。好了，以上是我的全部理解。博客freshman，如有錯誤，還請指點！

AC代碼：僅供參考

#include<bits/stdc++.h>
using namespace std;
#define p pair<int, char>
int n,m,data;
bool e[27][27],node[27];
string s;
inline void floyd(){
	for(int k=1; k<=n; k++){
		for(int i=1; i<=n; i++){
			for(int j=1; j<=n; j++){
				e[i][j] = e[i][j] || (e[i][k] && e[k][j]);
				if(e[i][j] && e[j][i] && i!=j){
					data = 0;
				}
			}
		}
	}
}
bool check(){
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			if(!e[i][j] && !e[j][i] && i!=j) return 0;
		}
	}
	return 1;
}
inline void out(){
	priority_queue<p, vector<p>, less<p> > q;
	int t;
	for(int i=1; i<=n; i++){
		t = 0;
		for(int j=1; j<=n; j++){
			if(i != j) t += e[i][j];
		}
		q.push( (p){t, i-1+'A'} );
	}
	while(!q.empty()){
		printf("%c",q.top().second);
		q.pop();
	}
	printf(".\n");
}
int main(){
	while(scanf("%d%d",&n,&m) && n){
		memset(e, 0, sizeof(e));
		memset(node, 0, sizeof(node));
		data = 1;
		for(int i=1; i<=m; i++){
			cin>>s;
			e[s[0]-'A'+1][s[2]-'A'+1] = 1;
			node[s[0]-'A'+1] = node[s[2]-'A'+1] = 1;
			if(data == 1){
				floyd();
				if(data == 0){
					printf("Inconsistency found after %d relations.\n",i);
					//break;
				}
				else if(check()){
					printf("Sorted sequence determined after %d relations: ",i);
					out();
					data = 2;
					//break;
				}
			}
		}
		if(data == 1){
			printf("Sorted sequence cannot be determined.\n");
		}
	}
}