首页 > 代码库 > Uva 10129 单词
Uva 10129 单词
题目链接：https://uva.onlinejudge.org/external/101/10129.pdf
把单词的首字母和最后一个字母看做节点，一个单词就是一个有向边。有向图的欧拉定理，就是除了起点和终点外，其他的点，出度等于入度，而且，起点和终点的出度和入度相差 1 ，这个在上一篇文章中证明了。
然后就是查连通：
1、DFS ——从一个点出发，搜索所有相邻的边，继续dfs(v)并标记，最后查图，是不是所有点都标记了。
2、并查集 ——最多有26个块，有一条新边来了，并且，祖先不同，就相连，并且，块减 1 ，最后排除那些没有出现的点后，看是不是只有一个块了。
#include <bits/stdc++.h>using namespace std;const int Maxn = 1000;int father[Maxn];int degree[Maxn];int used[Maxn];int Find_Set(int x){ if(x!=father[x]) father[x] = Find_Set(father[x]); return father[x];}int main(){ int T; scanf("%d",&T); while(T--) { int n; scanf("%d",&n); char str[1005]; memset(used,0,sizeof(used)); memset(degree,0,sizeof(degree)); for(int a=‘a‘;a<=‘z‘;a++) father[a] = a; int flag = 26; for(int i=0;i<n;i++) { scanf("%s",str); char c1 = str[0]; char c2 = str[strlen(str)-1]; used[c1] = used[c2] = 1; degree[c1] ++; degree[c2] --; int fx = Find_Set(c1); int fy = Find_Set(c2); if(fx!=fy) { father[fy] = fx; flag --; } } vector<int> vaj; for(int a = ‘a‘;a<=‘z‘;a++) if(!used[a]) flag--; else { if(degree[a]!=0) vaj.push_back(degree[a]); } sort(vaj.begin(),vaj.end()); if(flag!=1) puts("The door cannot be opened."); else if(vaj.size()==0||(vaj.size()==2&&vaj[0]==-1&&vaj[1]==1)) puts("Ordering is possible."); else puts("The door cannot be opened."); } return 0;}
Uva 10129 单词
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。