1 // 把一个图的所有结点排序，使得每一条有向边(u,v)对应的u都排在v的前面。 2 // 在图论中，这个问题称为拓扑排序。(toposort) 3 // 不难发现：如果图中存在有向环，则不存在拓扑排序，反之则存在。 4 // 不包含有向环的有向图称为有向无环图(DAG)。 5 // 可以借助DFS完成拓扑排序：在访问完一个结点之后把它加到当前拓扑序的首部。 6 7 int c[maxn]; 8 int topo[maxn],t; 9 bool dfs(int u) 10 { 11 c[u]=-1;//访问标志 12 for(int v=0;v<n;v++) 13 if(G[u][v]) 14 { 15 if(c[v]<0) return false;//存在有向环，失败退出 16 else if(!c[v]&&!dfs(v)) return false; 17 } 18 c[u]=1; 19 topo[--t]=u; 20 return true; 21 } 22 bool toposort() 23 { 24 t=n; 25 memset(c,0,sizeof(c)); 26 for(int u=0;u<n;u++) 27 { 28 if(!c[u]) 29 if(!dfs(u)) 30 return false; 31 } 32 return true; 33 } 34 35 // 这里用到了一个c数组，c[u]=0表示从来没有访问过（从来没有调用过dfs[u]） 36 // c[u]=1表示已经访问过，并且还递归访问过它的所有子孙（即dfs(u)曾被调用过并且已经返回） 37 // c[u]=-1表示正在访问（即递归调用dfs(u)正在栈帧中，尚未返回） 38 39 // 可以用DFS求出有向无环图(DAG)的拓扑排序。 40 // 如果排序失败，说明该图存在有向环，不是DAG。
UVA 1572
https://vjudge.net/problem/UVA-1572
题目大意：有些种类的正方形，每条边有两个符号，‘00‘’不能与任何边相连，只有字母相同，“+-”相反才能相连，让判断是否用这些已有的正方形铺成无限大的平面
解题思路：将字母装华为数字例如A+A-转化为2n，2n+1，这样如果一个正方形x（A+）能和另一个正方形y（A-）相连，则正方形x每个边都能到达正方形y（A+A-连接了以后A+这个正方形就与y相连了，所以x的任一边都考可到达y），想判断是否能无限大，则三角形必须重复出现（即他们之间的连接点会重复出现，在有向图中存在环，现在只需判断是否能形成有向环，如已经有A+A-相连，再发现一个A+A-相连，这之间是一个重复的过程，则可以无限循环下去）
1 #include <iostream> 2 #include <algorithm> 3 #include <string> 4 #include <sstream> 5 #include <set> 6 #include <vector> 7 #include <stack> 8 #include <map> 9 #include <queue> 10 #include <deque> 11 #include <cstdlib> 12 #include <cstdio> 13 #include <cstring> 14 #include <cmath> 15 #include <ctime> 16 #include <functional> 17 using namespace std; 18 19 #define maxn 60 20 char s[9]; 21 int g[maxn][maxn], vis[maxn], n; 22 23 int id(char a1, char a2) //将正方形的每一条边都进行赋值，使其称为图中的结点 24 { 25 //将每条边转化为2n或者2n+1的形式 26 return (a1 - 'A') * 2 + (a2 == '+' ? 0 : 1); 27 } 28 29 void connect(char a1,char a2,char b1,char b2) //将配对的结点连边，为有向图建模 30 { 31 // 边的对应关系： 32 // A+ <<-->> A- 所以(a1,a2)一定能和(a1,a2)^1配对连接 33 // 又因为(a1,a2)与(b1,b2)存在于同一个正方形，他们两个也一定能连接 34 // 所以 (a1,a2)^1 <<-->>(b1,b2) 35 if(a1=='0'||b1=='0') 36 return ; 37 int u=id(a1,a2)^1; 38 int v=id(b1,b2); 39 g[u][v]=1; 40 } 41 bool dfs(int u) 42 { 43 vis[u]=-1;//表示结点u正在访问中 44 for(int i=0;i<maxn;i++) 45 if(g[u][i]) 46 if(vis[i]==-1) return true;//在DFS的过程中访问到一个点也是-1，则说明这个点重复出现了，构成了有向环 47 else if(!vis[i]&&dfs(i)) //向深处递归，如果这个点未访问， 48 return true; //则访问它并且DFS判断它是否重复出现构成有向环 49 vis[u]=1;//访问结束变成1 50 return false; 51 } 52 bool judge() 53 { 54 memset(vis,0,sizeof(vis)); 55 for(int i=0;i<maxn;i++) 56 if(!vis[i])//只找到一个环即可 57 if(dfs(i)) return true; 58 return false; 59 } 60 int main() 61 { 62 while(~scanf("%d",&n)&&n) 63 { 64 memset(g,0,sizeof(g)); 65 while(n--) 66 { 67 cin>>s; 68 for(int i=0;i<4;i++) 69 for(int j=0;j<4;j++) 70 if(i!=j) 71 connect(s[i*2],s[i*2+1],s[j*2],s[j*2+1]);//同一个正方向的边互相建立联系 72 } 73 if(judge()) 74 cout<<"unbounded"<<endl; 75 else 76 cout<<"bounded"<<endl; 77 } 78 return 0; 79 }