AcWing 343. Sorting problem solution (Floyd property realizes transitive closure)

AcWing 343. Sort
utilize floyd The triple loop implements closure passing , Learned , Use the shortest path property to realize other functions

#include<bits/stdc++.h>

using namespace std;

const int N = 26;

bool d[N][N], g[N][N], st[N];
int n, m;

void floyd(){
    
	memcpy(d, g, sizeof g);
	for(int k = 0; k < n; k ++ ){
    
		for(int i = 0; i < n; i ++ ){
    
			for(int j = 0; j < n; j ++ ){
    
				d[i][j] |= d[i][k] && d[k][j];
			}
		}
	}
}

int check(){
    
	for(int i = 0; i < n; i ++ ){
    
		if(d[i][i]) return 2;  // contradiction  
	} 
	// The relationship is uncertain  
	for(int i = 0; i < n; i ++ ){
    
		for(int j = 0; j < i; j ++ ){
    
			if(!d[j][i] && !d[i][j]) return 0;  // The letters in front are not necessarily small , So both positive and negative should be judged 
		}
	}
	
	return 1;
}

char get_min(){
    
	for(int i = 0; i < n; i ++ ){
    
		if(!st[i]){
    
			bool flag = true;
			for(int j = 0; j < n; j ++ ){
    
				if(!st[j] && d[j][i]){
    
					flag = false;
					break;
				}	
			}
			// Output after traversing all the letters  
			if(flag){
    
				st[i] = true; 
				return i + 'A';
			}			
		}
	}
}

int main()
{
    
	while(cin>>n>>m, m || n){
    
		memset(g, 0, sizeof g);
		int type = 0, t; 
		for(int i = 1; i <= m; i ++ ){
    
			char str[5];
			cin>>str;
			int a = str[0] - 'A', b = str[2] - 'A';  // Convert characters to numbers  
			if(!type){
    
				g[a][b] = 1;
				floyd();  // Add new relationship 
				type = check();
				if(type) t = i;
			}
		}
		if(!type) cout<<"Sorted sequence cannot be determined."<<endl;
		else if(type == 2) cout<<"Inconsistency found after "<<t<<" relations."<<endl;
		else{
    
			cout<<"Sorted sequence determined after "<<t<<" relations: ";
			memset(st, 0, sizeof st);
			for(int i = 0; i < n; i ++ ){
    
				cout<<get_min();
			}
			cout<<"."<<endl;
		}
	}
	return 0;
}