首页 > 代码库 > uvalive 6393(uva 1572) Self-Assembly 拓扑排序

uvalive 6393(uva 1572) Self-Assembly 拓扑排序

题意:

给出一些正方形,这些正方形的每一条边都有一个标号,这些标号有两种形式:1.一个大写字母+一个加减号(如:A+, B-, A-......), 2.两个0(如:00);这些正方形可以随意翻转和旋转,当两个正方形通过旋转或翻转,使得他们的公共边为相同大写字母并且符号相反时,他们就可以彼此结合拼在一起,现在给出n中正方形,每种正方形有无限多种,问这些正方形能否拼成一个无限大的结构。

题解:

容易想到,要使这些正方形形成无限大地结构,那么这些正方形通过拼接后一定能循环(即通过不断地拼接出现了和以前相同地正方形),那么就可以通过判断将这些正方形地所有可能地拼接方式连有向边,然后判断是否有有向环,即可通过拓扑排序来判断。

代码:

#include <queue>
#include <vector>
#include <cstdio>
#include <string>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 52 + 10;
int G[maxn][maxn], vis[maxn];

int ID(char a, char b)
{
    return (a - 'A')*2 + (b == '+' ? 0 : 1);
}
void conect(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] = 1;
}
bool dfs(int u)
{
    vis[u] = -1;
    for (int v = 0; v < 52; v++) if (G[u][v])
    {
        if (vis[v] == -1) return true;
        if (!vis[v] && dfs(v)) return true;
    }
    vis[u] = 1;
    return false;
}
bool find_cycle()
{
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < 52; i++) if (!vis[i])
    {
        if (dfs(i)) return true;
    }
    return false;
}
int main()
{
 //   freopen("/Users/apple/Desktop/in.txt", "r", stdin);
    int n;
    while(scanf("%d", &n) == 1 && 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)
                {
                    conect(s[i*2], s[i*2+1], s[j*2], s[j*2+1]);
                }
            }
        }
        if (find_cycle()) printf("unbounded\n");
        else printf("bounded\n");
    }

    
    return 0;
}


uvalive 6393(uva 1572) Self-Assembly 拓扑排序