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分钟，我也不到，但愿不会点名吧
等会把欧拉回路总结一下吧