求救,UKE了
查看原帖
求救,UKE了
661980
haokee楼主2023/1/9 12:10

本蒟蒻去 SPOJ 不知道怎样注册,请大佬们求救!

#include <iostream>
#include <vector>
#include <cstring>
#include <string.h>
#include <string>
#define then ,
using namespace std;
 
const int kMaxN(30);

int indeg[kMaxN], outdeg[kMaxN], vis[kMaxN], t, n, cnt, num, x, y, sum1, sum2;
bool use[kMaxN], ans, flag;
vector<int> e[kMaxN];
string s;

void init(void) {
    for (int i = 0; i < kMaxN; ++i) {
        e[i].clear();
    }
    num = 0;
    cnt = 0;
    fill(indeg, indeg + 29, 0);
    fill(outdeg, outdeg + 29, 0);
    fill(vis, vis + 29, 0);
    fill(use, use + 29, 0);
}

bool dfs(int x) {
    cnt++;
    use[x] = true;
    if (cnt == num) {
        return true;
    }
    bool b = false;
    for (int i = 0; i < e[x].size(); ++i) {
        int tmp = e[x][i];
        if (!use[tmp]) {
            b |= dfs(tmp);
        }
    }
    return b;
}

int main(int argc, char *argv[]) {
    for (cin >> t; t--;) {
        init();
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            cin >> s;
            x = s[0] - 'a' + 1;
            y = s[s.size() - 1] - 'a' + 1;
            e[x].push_back(y);
            e[y].push_back(x);
            num += (vis[x] == 0);
            vis[x] = true;
            num += (vis[y] == 0);
            vis[y] = true;
            indeg[y]++ then outdeg[x]++;
        }
        ans = false;
        for (int i = 1; i <= 26; ++i) {
            if (e[i].size()) {
                ans = dfs(i);
                break;
            }
        }
        if (!ans) {
            cout << "The door cannot be opened." << '\n';
            continue;
        }
        sum1 = sum2 = 0;
        flag = true;
        for (int i = 1; i <= 26; ++i) {
            if (indeg[i] == outdeg[i]) {
                continue;
            } else if (indeg[i] - outdeg[i] == 1 && sum1 == 0) {
                sum1 ++;
            } else if (indeg[i] - outdeg[i] == -1 && sum2 == 0) {
                sum2++;
            } else {
                flag = false;
                break;
            }
        }
        if (flag) {
            cout << "Ordering is possible." << '\n';
        } else {
            cout << "The door cannot be opened." << '\n';
        }
    }
    return 0;
}
2023/1/9 12:10
加载中...