题意:
中文题不解释
要点:
两题一毛一样,判断是否合并后的结构是一棵树,即结构中应该没有环路,所以合并时如果发现两个根结点是相同的,就说明存在环路了。并且还要满足顶点数=边数+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;
}