首页 > 代码库 > HDU 1325 Is It A Tree?
HDU 1325 Is It A Tree?
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1325
解析:
首先,我不得不吐槽一下,这题又是一个没有数据范围的题目,尼玛啊,只能慢慢地去尝试。
然后,我想说一下这个题目真的考虑的问题很多,是一个难度较高的并查集问题。
并查集在这里就不多说了,就谈一谈怎么去去判断吧!这里我们要判断是否是一棵树树,那么就不能出现环和森林。另外,这里的树枝是有方向的,所以每个点的入度不能大于1。
但是,我这里还存在着一个疑问,当我将判断入度的表达式放在判断是否是一棵树的循环里的时候,给的答案是WA的,但是当我把他在并查语句后面判断的时候就是正确的,有没有人能够解释一下这其中的问题呢?
在这里给出几个坑爹的数据
//数据: 0 0 1 1 0 0 1 2 2 1 0 0 1 2 2 3 3 4 4 1 0 0 1 2 2 3 3 1 5 6 0 0 1 2 2 3 4 3 0 0 1 2 2 3 5 6 0 0 2 3 0 0 //答案: Case 1 is a tree. Case 2 is a tree. Case 3 is not a tree.//环 Case 4 is not a tree.//环 Case 5 is not a tree. Case 6 is not a tree.//节点3入度大于1 Case 7 is not a tree.//两棵树 Case 8 is a tree.
代码:
/* ID:muller8 Name: 1325 Is It A Tree? Reference: 并查集 */ #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <vector> #include <cmath> #include <vector> using namespace std; #define MAXN 100010 #define INF 1e9 int fa[MAXN]; int in[MAXN]; bool visit[MAXN]; vector<int> vec; //保存所有的节点 void init(){ memset(in,0,sizeof(in)); memset(visit,false,sizeof(visit)); vec.clear(); for(int i=0;i<MAXN; ++i) fa[i] = i; } int find(int n){ if(fa[n]!=n) fa[n] = find(fa[n]); return fa[n]; } int main(){ int x,y; bool flag = true; int Case = 0; init(); while(~scanf("%d%d", &x,&y)){ if(x<0&&y<0) break; if(0==x&&0==y){ if(flag){ if(vec.size()){ int tmp = find(vec[0]); for(int i=1; i<vec.size(); ++i) //判断是否只有一棵树 if(tmp!=find(vec[i])){ flag = false; break; } } } printf("Case %d is %s\n", ++Case, flag?"a tree.":"not a tree."); flag = true; init(); continue; } //用一个vector来保存所有出现过的节点 if(!visit[x]){ visit[x] = true; vec.push_back(x); } if(!visit[y]){ visit[y] = true; vec.push_back(y); } if(!flag) continue; //如果已经不是一棵树了,也就不必要太多的操作 if(x==y) continue; //如果是同一个点也不用进行运算,当然这里是防止坑爹数据的 int fx, fy; fx = find(x); fy = find(y); if(fx == fy){ flag = false; continue; } else{ fa[fx] = fy; in[y]++; } if(in[y]>1) flag = false; //入度大于1,flag为否 } return 0; }
在这里给出几个坑爹的数据
HDU 1325 Is It A Tree?
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。