6 16_play_on_words_uva10129 - nuaazdh/acm GitHub Wiki

##例题6-16 单词游戏（Play on Words UVa10129） ###问题给定一系列单词，判断这些单词是否可以能够全部首尾相连。如单词acm、malform和mouse可以首尾相连，但是acm和ibm就不可以。

输入第一行为测试case 的个数，后面每个case以一个正整数开头，表示case 中单词的数目，输出参照样例。

样例输入

3
2
acm
ibm
3
acm
malform
mouse
2
ok
ok

样例输出

The door cannot be opened.
Ordering is possible.
The door cannot be opened.

###分析

开始把问题想得太简单，直接统计单词首字母和末尾字母的出现的次数，在词首作为入度，在词尾作为出度。如果每个字母（一共26个）的入度和出度相同，则可以，否则最多两个字母的出度和入度不等。

WA，反例： ok ok

尝试加一条判断，不能有任何一个字母的出度和入度只差大于1.

WA，反例：abc ad,da, 这个可以构成了两个回路。

最后发现原来这个必须考虑欧拉回路，根据欧拉回路的条件，首先强连通（SCC只有一个），其次出度和入度相同，奇点不超过2个。

其中强连通怎么求？一查，都知道并查集和DFS。其实就是判断一个有向图的连通分量，有 Tarjan 和 Kosaraju 两种算法。这两个算法求出一个有向图的全部SCC。我们不用这么复杂，直接一个**拓扑排序**，然后最后一个入栈的元素开始，可以遍历整个有向图即可。

###code in C++

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stack>

const int alpha_size = 26;
int graph[alpha_size][alpha_size], visit[alpha_size];
int vetex[alpha_size];


void dfs(int v, std::stack<int> &stack) {
//    printf("call dfs at :%c\n", v+'a');
    if (visit[v])
        return;;
    visit[v] = 1;
    for (int i = 0; i < alpha_size; ++i) {
        if (graph[v][i] && !visit[i])
            dfs(i, stack);
    }
//    printf("push:%c\n", v + 'a');
    stack.push(v);
}

void dfs2(int v) {
    if (visit[v])
        return;
    visit[v] = 1;
    for (int i = 0; i < alpha_size; ++i) {
        if (graph[v][i] && !visit[i])
            dfs2(i);
    }
}

int check_scc() {
    memset(visit, 0, sizeof(visit));
    std::stack<int> stack;
    for (int i = 0; i < alpha_size; ++i) {
        if (vetex[i] && !visit[i])
            dfs(i, stack);
    }
    memset(visit, 0, sizeof(visit));
    if (!stack.empty()) {
        int top = stack.top();
//        printf("pop:%c\n", stack.top() + 'a');
        stack.pop();
        dfs2(top);
        while (!stack.empty() && visit[stack.top()]) {
//            printf("pop:%c\n", stack.top() + 'a');
            stack.pop();
        }
    }
    return stack.empty();
}

void print_graph() {
    for (int i = 0; i < alpha_size; ++i) {
        for (int j = 0; j < alpha_size; ++j) {
            if (graph[i][j])
                printf("%c -> %c\n", i + 'a', j + 'a');
        }
    }
}


int check_degree() {
    int in_out_not_equal_cnt = 0;
    for (int i = 0; i < alpha_size; ++i) {
        int in_d = 0, out_d = 0;
        for (int j = 0; j < alpha_size; ++j) {
            in_d += graph[i][j];
            out_d += graph[j][i];
        }
        if (abs(in_d - out_d) > 1) {
//            printf("in > out +1: %c\n", i + 'a');
            return 0;
        }
        if (in_d != out_d) ++in_out_not_equal_cnt;
        if (in_out_not_equal_cnt > 2) {
//            printf("not equal more than 2, %d %d\n", in_d, out_d);
            return 0;
        }
    }
    return 1;
}


int main() {
    int T;
    std::cin >> T;
    std::string impossible = "The door cannot be opened.\n", possible = "Ordering is possible.\n";
    while (T--) {
        int n;
        std::cin >> n;
        memset(graph, 0, sizeof(graph));
        memset(vetex, 0, sizeof(vetex));
        std::string word;
        while (n--) {
            std::cin >> word;
            if (!word.empty()) {
                int start = tolower(word[0]) - 'a', ends = tolower(word[word.length() - 1]) - 'a';
                ++graph[start][ends];
                ++vetex[start];
                ++vetex[ends];
            }
        }
//        print_graph();
        if (check_scc() && check_degree()) {
            std::cout << possible;
        } else {
            std::cout << impossible;
        }
    }
}

###点评

算一个简单的实现，但是不够简洁，两次DFS调用，而且不同代码；
计算出度和入度的其实可以在读入单词的时候就统计；

###改进

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <stack>

const int alpha_size = 26;
int graph[alpha_size][alpha_size], visit[alpha_size], first[alpha_size], last[alpha_size];


void dfs(int v, std::stack<int> &stack) {
    visit[v] = 1;
    for (int i = 0; i < alpha_size; ++i) {
        if (graph[v][i] && !visit[i])
            dfs(i, stack);
    }
    stack.push(v);
}

void dfs2(int v) {
    visit[v] = 1;
    for (int i = 0; i < alpha_size; ++i) {
        if (graph[v][i] && !visit[i])
            dfs2(i);
    }
}

int check_scc() {
    memset(visit, 0, sizeof(visit));
    std::stack<int> stack;
    for (int i = 0; i < alpha_size; ++i) {
        if ((first[i] | last[i]) && !visit[i])
            dfs(i, stack);
    }
    memset(visit, 0, sizeof(visit));
    if (!stack.empty()) {
        int top = stack.top();
        stack.pop();
        dfs2(top);
        while (!stack.empty() && visit[stack.top()]) stack.pop();
    }
    return stack.empty();
}

int check_degree() {
    int in_out_not_equal_cnt = 0;
    for (int i = 0; i < alpha_size; ++i) {
        if ((first[i] - last[i] > 1) || (last[i] - first[i] > 1)) {
            return 0;
        }
        if (first[i] != last[i]) ++in_out_not_equal_cnt;
        if (in_out_not_equal_cnt > 2) {
            return 0;
        }
    }
    return 1;
}


int main() {
    int T;
    std::cin >> T;
    std::string impossible = "The door cannot be opened.\n", possible = "Ordering is possible.\n";
    while (T--) {
        int n;
        std::cin >> n;
        memset(graph, 0, sizeof(graph));
        memset(first, 0, sizeof(first));
        memset(last, 0, sizeof(last));
        std::string word;
        while (n--) {
            std::cin >> word;
            if (!word.empty()) {
                int start = tolower(word[0]) - 'a', ends = tolower(word[word.length() - 1]) - 'a';
                ++graph[start][ends];
                ++first[start];
                ++last[ends];
            }
        }
        if (check_scc() && check_degree()) {
            std::cout << possible;
        } else {
            std::cout << impossible;
        }
    }
}

6 16_play_on_words_uva10129 - nuaazdh/acm GitHub Wiki

⚠️ **GitHub.com Fallback** ⚠️

⚠️ GitHub.com Fallback ⚠️