//分析解決方案很明顯的一個用并查積解決的問題：如果只用一個根肯定滿足要求，遍歷數組即可
//如果某兩個要合并的節點同根肯定會構成回路，不滿足要求
這里用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
雪黛依夢 閱讀(835)
評論(1) 編輯 收藏 引用 所屬分類:
并查積