我用的是并查集来ac的。
这个和以前的题目有所不同
抽象来说 这属于有向图
所以不能有路径优化那一步 因为那一步是看作无向图来操作的
另外这道题要注意 是 多组输入
题目链接————》》 hdu 1181
AC代码：
#include<iostream> #include<cstdio> using namespace std; int f[30]; int find(int index){ int k = index; while (f[k] != k){ k = f[k]; } int m = index,temp; /*while (f[m] != k){ temp = f[m]; f[m] = k; m = temp; }*/ return k; } void join(int a,int b){ int ina, inb; ina = find(a); inb = find(b); if (ina != inb){ f[ina] = inb; } } int judge(){ // int mark = 0; int k = 'b' - 96, m = 'm' - 96;; while (f[k] != m && f[k]!=k){ k = f[k]; } if (f[k] != m){ return 0; } return 1; } int main(){ // freopen("TestDate.txt", "r", stdin); char s[1000]; int i; while (true){ for (i = 0; i < 30; i++){ f[i] = i; } int mark = -1; while (cin >> s){ if (s[0] == '0'){ mark = 1; break; } for (i = 1; s[i] != '\0'; i++); join(s[0] - 96, s[i-1] - 96); } if (mark != 1){ break; } if (judge()){ cout << "Yes." << endl; } else{ cout << "No." << endl; } } return 0; }