Play on Words（UVA 10129）

网址如下：

Play on Words - UVA 10129 - Virtual Judge (vjudge.net)

（第三方网站）

一道关于有向欧拉回路的题，其中字母为节点，单词为道路

满足存在欧拉回路的条件有两个：

1，最多有两个奇点（入度和出度不相同的点），同时入度和出度的绝对值相差不能超过1

2，所有节点在不管方向的时候连通

对于第一个条件，只要统计计算就可以了

对于第二个条件，bfs和dfs都可以

代码如下：

#include<cstdio>
#include<cstring>
#include<set>
#include<queue>
#include<cmath>
void scanf_input(void);
bool bfs(void);
int indegree[26], outdegree[26];
std::set<int> cnt1, cnt2;
bool G[26][26];

int main(void)
{
    int kase; scanf("%d", &kase);
    while(kase--){
        memset(indegree, 0, sizeof(indegree));
        memset(outdegree, 0, sizeof(outdegree));
        memset(G, 0, sizeof(G));
        int n; scanf("%d", &n); getchar();
        for(int i = 0; i < n; i++)
            scanf_input();
        //判断出入度
        int sig = 0; bool is_judge = true;
        for(int i = 0; i < 26; i++)
            if(indegree[i] != outdegree[i])
                if(++sig > 2 || abs(indegree[i] - outdegree[i]) > 1)
                    {printf("The door cannot be opened.\n"); is_judge = false; break;}
        if(!is_judge) continue;
        //判断是否连通
        cnt1.clear(); cnt2.clear();
        for(int i = 0; i < 26; i++) if(indegree[i] || outdegree[i]) cnt1.insert(i);
        if(bfs()) printf("Ordering is possible.\n");
        else printf("The door cannot be opened.\n");
    }
}
void scanf_input(void)
{
    char fc = getchar(), bc;
    int u = fc -'a', v; outdegree[u]++;
    do{bc = fc; fc = getchar();}while(fc != '\n');
    v = bc - 'a'; indegree[v]++;
    G[u][v] = G[v][u] = true;
}
bool bfs(void)
{
    int u = 0; while(!indegree[u] && !outdegree[u]) u++;
    std::queue<int> q;
    q.push(u); cnt2.insert(u);
    while(!q.empty()){
        u = q.front(); q.pop();
        for(int v = 0; v < 26; v++)
            if(G[u][v]){G[u][v] = G[v][u] = false; cnt2.insert(v); q.push(v);}
    }
    if(cnt1 == cnt2) return true;
    else return false;
}

我这里是用了bfs来判断是否连通

一点废话：

今天翘掉了两节课，使得今天成为工作日中最轻松的一天，只有一节高代课，至于那两节课嘛。。。我听说乡村振兴概论课已经人少到一眼看出一堆人翘课了，至于下午的中国近现代史纲要嘛。。。这才刚上课11分钟，我也不到，但愿不会点名吧

等会把欧拉回路总结一下吧