有向图找环
1 #include<cstdio> 2 #include<cstring> 3 int map[27][27],indegree[27],q[27]; 4 int TopoSort(int n){ 5 int t=0,temp[27],p,m,flag=1; //flag=1:有序 flag=-1:不确定 6 for(int i=1;i<=n;i++)temp[i]=indegree[i]; 7 for(int i=1;i<=n;i++){ 8 m=0;for(int j=1;j<=n;j++)if(temp[j]==0)m++,p=j;//查找入度为零的顶点个数 9 if(m==0)return 0; //有环 10 if(m>1) flag=-1; //无序 11 q[++t]=p,temp[p]=-1;//入度为零的点入队 12 for(int j=1;j<=n;j++)if(map[p][j]==1)temp[j]--; 13 } 14 return flag; 15 } 16 int main(){ 17 int n,m,sign,x,y; 18 for(char s[5];scanf("%d%d",&n,&m)!=EOF;){ 19 if(n==0&&m==0)break; 20 memset(map,0,sizeof(map)),sign=0; 21 memset(indegree,0,sizeof(indegree)); 22 for(int i=1;i<=m;i++){ 23 scanf("%s",s); 24 if(sign)continue; 25 x=s[0]-'A'+1,y=s[2]-'A'+1; 26 map[x][y]=1,indegree[y]++; 27 int f=TopoSort(n); 28 if(f==0)sign=1,printf("Inconsistency found after %d relations. ",i); 29 if(f==1){ 30 sign=1,printf("Sorted sequence determined after %d relations: ",i); 31 for(int j=1;j<=n;j++)printf("%c",q[j]+'A'-1); 32 puts("."); 33 } 34 } 35 if(!sign)puts("Sorted sequence cannot be determined."); 36 } 37 return 0; 38 }
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 const int N = 30; 7 int n, m, d[N][N], e[N][N]; 8 9 int floyd() { 10 memcpy(e, d, sizeof(e)); 11 for (int k = 0; k < n; k++) 12 for (int i = 0; i < n; i++) 13 for (int j = 0; j < n; j++) { 14 e[i][j] |= e[i][k] & e[k][j]; 15 if (e[i][j] == e[j][i] && e[i][j] && i != j) return -1; 16 } 17 for (int i = 0; i < n; i++) 18 for (int j = 0; j < n; j++) 19 if (e[i][j] == e[j][i] && !e[i][j] && i != j) return 0; 20 return 1; 21 } 22 23 void Sorting_It_All_Out() { 24 memset(d, 0, sizeof(d)); 25 bool flag = 1; 26 for (int i = 1; i <= m; i++) { 27 char s[6]; 28 scanf("%s", s); 29 d[s[0]-'A'][s[2]-'A'] = 1; 30 if (flag) { 31 int now = floyd(); 32 if (now == -1) { 33 printf("Inconsistency found after %d relations. ", i); 34 flag = 0; 35 } else if (now == 1) { 36 printf("Sorted sequence determined after %d relations: ", i); 37 pair<int, char> ans[N]; 38 for (int j = 0; j < n; j++) { 39 ans[j].first = 0; 40 ans[j].second = 'A' + j; 41 } 42 for (int j = 0; j < n; j++) 43 for (int k = 0; k < n; k++) 44 if (e[j][k]) ++ans[j].first; 45 sort(ans, ans + n); 46 for (int j = n - 1; j >= 0; j--) printf("%c", ans[j].second); 47 puts("."); 48 flag = 0; 49 } 50 } 51 } 52 if (flag) puts("Sorted sequence cannot be determined."); 53 } 54 55 int main() { 56 while (cin >> n >> m && n) Sorting_It_All_Out(); 57 return 0; 58 }