单词是边，两端字母是节点，图有没有欧拉回路。判断图的连通性和各节点的度
#include <iostream>
#include <string>
#include <vector>
#include <cstring>
using namespace std;
const int maxn = 30;
int uset[26],used[26];
int degree[maxn];
void usetinit(){for(int i=0;i<26;i++)uset[i] = i;}
int find_root(int x){return uset[x] == x?x:uset[x] = find_root(uset[x]);}
int union_set(int x,int y){ uset[x] = y; }
int main(){
int t,n,a,b;
string s;
cin>>t;
while(t--){
cin>>n;
memset(degree,0,sizeof(degree));
memset(used,0,sizeof(used));
usetinit();
int cc = 26;
for(int i=0;i<n;i++){
cin>>s;
a = s[0] - 'a'; b = s[s.size() - 1] - 'a';
degree[a]--;
degree[b]++;
used[a]=used[b] = 1;
int r1 = find_root(a);int r2 = find_root(b);
if(r1 != r2){union_set(r1,r2);cc--;}
}
vector<int> ans;
for(int i=0;i<26;i++){
if(used[i] == 0)cc--;
else if(degree[i] != 0)ans.push_back(degree[i]);
}
if(cc==1&&(ans.empty() || (ans.size() == 2 && (ans[0] == 1 || ans[0] == -1))))cout<<"Ordering is possible.\n";
else cout<<"The door cannot be opened.\n";
}
system("pause");
return 0;
}
要求。所有节点出入度为零或者只有两个节点，总和有一个出度和一个入度
转载请注明原文地址: https://ju.6miu.com/read-1309191.html
