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博客 ，格式可能有所偏差。