UVa 1572 - Self-Assembly(拓扑排序)

输入n种边上带标号的正方形,特定标号可以相连,判断能否铺成无限大的结构。

书上的例题,给出了思路。将标号转化为点,将正方形看作边,得到有向图,对其进行拓扑排序,判断是否形成环即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int maxn=52;
int c[maxn];
bool g[maxn][maxn];
int id(char a1,char a2){//给每个标号分配id。
return (a1-'A')*2+(a2=='+'?0:1);
}
void connect(char a1,char a2,char b1,char b2){//将输入的正方形和标号转化为有向图。
if(a1=='0'||b1=='0') return;
int u=id(a1,a2)^1,v=id(b1,b2);
g[u][v]=true;
}
bool toposort(int u){//拓扑排序。
c[u]=-1;
for(int v=0;v<maxn;++v)
if(g[u][v]){
if(c[v]<0) return true;
else if(!c[v]&&toposort(v)) return true;
}
c[u]=1;
return false;
}
bool cycle(){
memset(c,0,sizeof(c));
for(int i=0;i<maxn;++i)
if(!c[i]) if(toposort(i)) return true;
return false;
}
int main(){
int n;
while(~scanf("%d",&n)&&n){
memset(g,0,sizeof(g));
while(n--){
char s[10];
scanf("%s",s);
for(int i=0;i<4;++i)
for(int j=0;j<4;++j)
if(i!=j) connect(s[i*2],s[i*2+1],s[j*2],s[j*2+1]);
}
printf("%s\n",cycle()?"unbounded":"bounded");//形成环不可拼出无限大。
}
return 0;
}

本文迁移自我的 CSDN博客 ,格式可能有所偏差。