题目大意:输入一系列的点，判断这些点组成的图符不符合小希的思路(无环、连通)
解题思路:
1)如果两个节点的根节点相同，那么在这两个节点之间添加1条边以后，这个图肯定有环路。
2)孤立节点:被使用过&&当前节点的父亲节点是自己
代码如下:
/*
* 1272_1.cpp
*
* Created on: 2013年8月23日
* Author: Administrator
*/ #include <iostream> using namespace std; /**
* father[i] : 用来保存当前节点的父节点
* flag[i] :判断当前节点是否使用过.
* ok : 判断该迷宫是否满足小希的思路
*/
int father[100005];//不要只开到100001,否则会WA
bool flag[100005];
bool ok;
int find(int a) {
if (a == father[a]) {
return a;
}
father[a] = find(father[a]); return father[a];
} void join(int x, int y) {
int fx = find(x);
int fy = find(y); /**
* 如果两个节点n、m的根节点相同,
* 那么在他们之间添加一条以后，这个图肯定出现了环路
*/
if (fx != fy) {
father[fx] = fy;
} else {
ok = false;
}
} void make_set() {
int i;
for (i = 1; i <= 100001; ++i) {
father[i] = i;
}
} int main() {
int n, m;
while (scanf("%d%d", &n, &m) != EOF, n != -1) {
if (n == 0) {
printf("Yes\n");
continue;
}
make_set();
memset(flag, 0, sizeof(flag)); flag[n] = true;
flag[m] = true;
ok = true;
join(n, m); while (scanf("%d%d", &n, &m) != EOF, n != 0) {
join(n, m);
flag[n] = true;
flag[m] = true;
} int i;
int count = 0;
for (i = 1; i <= 100001; ++i) {
/**
* 如果当前节点被使用过&&当前节点的父亲节点是他自己,
* 那么这个节点就是孤立节点(除了根节点)
*/
if (flag[i] && father[i] == i) {
count++;
} } if (count > 1) {
ok = false;
}
if (ok) {
printf("Yes\n");
} else {
printf("No\n");
}
}
}