//分析解决方案很明显的一个用并查积解决的问题：如果只用一个根肯定满足要求，遍历数组即可
//如果某两个要合并的节点同根肯定会构成回路，不满足要求
这里用sign 标记是否出现了同根，分两种情况处理即可，也WA 了几次，因为复制粘贴把那个求minn 和 maxn 弄错了
还有就是没处理一组输入的时候一定要避免上一组输入的影响，那就是初始化
其他的就是套用并查积的模板就可以了
#include <iostream>
#include <string>
using namespace std;
struct node
{
int parent;
int weight;
};
node maze[100001];
int visit[100001]; //是集合中的元素都被标记
int findfather ( int i )
{
while ( i != maze[i].parent )
i = maze[i].parent;
return i;
}
void merge ( int a, int b )
{
if ( maze[a].weight == maze[b].weight )
{
maze[b].parent = a;
maze[a].weight = b;
}
else if ( maze[a].weight > maze[b].weight )
maze[b].parent = a;
else
maze[a].parent = b;
}
int main ()
{
int a, b, a1, b1, sign;
while ( scanf ("%d %d", &a, &b) != EOF )
{
memset (visit , 0, sizeof (visit));
int maxn = 0;
int minn = 1000000;
//并查积算法的初始化
for ( int i = 1; i < 100001; i ++ )
{
maze[i].parent = i;
maze[i].weight = 1;
}
if ( a == -1 && b == -1 )
break;
if ( a == 0 && b == 0 )
{
printf ("Yes\n");
continue;
}
sign = 0;
do {
if ( a < minn ) minn = a; //找到输入 的所有数据中最小的和最大的便于减小最后数组遍历时的复杂度
if ( b < minn ) minn = b;
if ( a > maxn ) maxn = a;
if ( b > maxn ) maxn = b;
visit[a] = visit[b] = 1;
a1 = findfather (a);
b1 = findfather (b);
if ( a1 == b1 ) //节点同根
{
sign = -1;
}
else
merge (a1, b1);
scanf ("%d %d", &a, &b);
if ( a== 0 && b == 0)
break;
}while (1);
if ( sign == -1 )
{
printf ("No");
}
//遍历并查积看有几个根节点
if ( sign == 0 )
{
for (int i = minn; i <= maxn; i ++)
{
if ( visit[i] && maze[i].parent == i )
sign ++;
}
if (sign == 1)
printf ("Yes\n");
else
printf ("No\n");
}
}
//system ("pause");
return 0;
}
posted on 2010-08-26 10:41
雪黛依梦 阅读(822)
评论(1) 编辑 收藏 引用 所属分类:
并查积