UVa 1572 自组合 （Self-Assembly）

题目
有n种边上带标号的正方形。每条边要么为一个大写字母后面跟一个加号或者减号，要么为数字00。并且仅当两条边的字母相同且符号相反时，两条边能够拼在一起，00不能和任何包括00的边拼在一起。
假设输入的每种正方形都有无穷多个，而且可以旋转和翻转，任务是判断是否能够成一个无限大的结构，每条边要么悬空，要么和上述可拼接的边相邻。

要点

• 连接，看看能不能循环一个边，即能不能构成环，判断能不能在有向图里构成环，用拓扑排序检测，由于只有52个边，00情况不考虑，由于有00，必定不能构成环。

#include<bits/stdc++.h>
using namespace std;

//分别代表 A- B- C- D- E- F- G- ………… A+ B+ C+
int G[52][52];
int vis[52];

bool dfs(int i) {
    vis[i] = -1; //正在访问
    for(int j = 0; j < 52; j++) {
        if(G[i][j]) {
            if(vis[j] == -1) {
                //cout << i << "*" << j << endl; 
                return false;
            }//环
            if(!vis[j] && !dfs(j)) return false;
        }
    }
    vis[i] = 1;
    return true;
}

bool topSort() {
    for(int i = 0; i < 52;i ++) {
        if(!vis[i]) {
            if(!dfs(i))
                return false;
        }
    }
    return true;
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    while(cin >> n) {
        string s;
        string temp[4];
        memset(vis, false, sizeof(vis));
        memset(G, 0, sizeof(G));
        //构造有向边
        for(int i = 0; i < n; i++) {
            cin >> s;
            temp[0] = s.substr(0, 2);
            temp[1] = s.substr(2, 2);
            temp[2] = s.substr(4, 2);
            temp[3] = s.substr(6, 2);
            for(int j = 0; j < 4; j++) {
                for(int k = 0; k < 4; k++) {
                    if(j == k) continue;
                    if(temp[j] == "00" || temp[k] == "00") continue;
                    int index1 = temp[j][0] - 'A' + (temp[j][1] == '-' ? 0 : 26);
                    int index2 = temp[k][0] - 'A' + (temp[k][1] == '+' ? 0 : 26);
                    G[index1][index2] = 1;
                    //cout << index1 << " " << index2 << endl;
                }
            }
        }
        if(!topSort()) {
            cout << "unbounded" << endl;
        }
        else {
            cout << "bounded" << endl;
        }
    }
}