当前位置: 代码迷 >> 综合 >> HDU1272POJ1308 小希的迷宫Is It A Tree?(并查集)
  详细解决方案

HDU1272POJ1308 小希的迷宫Is It A Tree?(并查集)

热度:31   发布时间:2024-01-16 13:49:47.0

题意:

中文题不解释

要点:

两题一毛一样,判断是否合并后的结构是一棵树,即结构中应该没有环路,所以合并时如果发现两个根结点是相同的,就说明存在环路了。并且还要满足顶点数=边数+1。这题比较恶心的地方在于,如果一开始输入0,0要输出Yes,输入部分比较难写,而且HDU改题的时候还没提这事,POJ上倒是有说明。


HDU1272:

16711170 2016-03-29 13:50:08 Accepted 1272 62MS 3368K 1009 B C++ seasonal

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define maxn 100050
int p[maxn];
bool valid,mark[maxn];
int edge;void init()
{valid = true;edge = 0;memset(mark, false, sizeof(mark));for (int i = 1; i < maxn; i++)p[i] = i;
}
int find(int x)
{if (p[x] == x) return x;return p[x] = find(p[x]);
}
void merge(int x, int y)
{int xx = find(x);int yy = find(y);if (xx == yy){ valid = false;return;}mark[x] = true;mark[y] = true;edge++;p[xx] = yy;
}int main()
{int x, y;while (~scanf("%d%d", &x, &y)){if (x == -1 && y == -1)break;if (x == 0 && y == 0)	//一开始就是0,0必须输出Yes{printf("Yes\n");continue;}init();merge(x, y);while (~scanf("%d%d", &x, &y)){if (x == 0 && y == 0)break;merge(x, y);}int node = 0;for (int i = 1; i < maxn; i++)if (mark[i])node++;if (!valid || (node != edge + 1))printf("No\n");elseprintf("Yes\n");}return 0;
}

POJ1308:

15330358 Seasonal 1308 Accepted 828K 0MS G++ 1040B 2016-03-29 21:59:45
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define maxn 100050
int p[maxn];
bool valid,mark[maxn];
int edge;void init()
{valid = true;edge = 0;memset(mark, false, sizeof(mark));for (int i = 1; i < maxn; i++)p[i] = i;
}
int find(int x)
{if (p[x] == x) return x;return p[x] = find(p[x]);
}
void merge(int x, int y)
{int xx = find(x);int yy = find(y);if (xx == yy){ valid = false;return;}mark[x] = true;mark[y] = true;edge++;p[xx] = yy;
}int main()
{int x, y,kase=1;while (~scanf("%d%d", &x, &y)){if (x == -1 && y == -1)break;if (x == 0 && y == 0)	//一开始就是0,0必须输出Yes{printf("Case %d is a tree.\n", kase++);continue;}init();merge(x, y);while (~scanf("%d%d", &x, &y)){if (x == 0 && y == 0)break;merge(x, y);}int node = 0;for (int i = 1; i < maxn; i++)if (mark[i])node++;if (!valid || (node != edge + 1))printf("Case %d is not a tree.\n",kase++);elseprintf("Case %d is a tree.\n",kase++);}return 0;
}


  相关解决方案