uva1572（拓扑）

题目连接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4364

注意条件是可以旋转或者翻转，，

每条边看作点，两个正方形相连的边看作连接两点的有向边

拓扑排序

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<vector>
 4 using namespace std;
 5 int p[55][55];
 6 int c[55];
 7 char s[10];
 8 
 9 int ID(char a,char b)
10 {
11     return (a-'A')*2+(b=='+'?0:1);
12 }
13 void connect(char a1,char a2,char b1,char b2)
14 {
15     if(a1=='0'||b1=='0') return;
16     int u=ID(a1,a2)^1,v=ID(b1,b2); //异或是取对应边
17     p[u][v]=1; //因为可以翻转，对应边皆可达
18 
19 }
20 
21 bool dfs(int u)
22 {
23     c[u]=-1;
24     for(int v=0;v<52;v++) if(p[u][v])
25     {
26         if(c[v]<0) return 1;
27         else if(!c[v]&&dfs(v)) return 1;
28     }
29     c[u]=1;
30     return 0;
31 }
32 bool fcircle()
33 {
34     memset(c,0,sizeof(c));
35     for(int i=0;i<52;i++)
36         if(dfs(i)) return 1;
37     return 0;
38 }
39 int main()
40 {
41     int n;
42     while(scanf("%d",&n)!=EOF&&n)
43     {
44         memset(p,0,sizeof(p));
45         while(n--)
46         {
47             scanf("%s",s);
48             for(int i=0;i<4;i++)
49                 for(int j=0;j<4;j++) if(i!=j)
50             connect(s[i*2],s[i*2+1],s[j*2],s[j*2+1]); //
51         }
52         if(fcircle()) puts("unbounded");
53         else puts("bounded");
54     }
55 }