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 }