首页 > 代码库 > UVa 615 - Is It A Tree?
UVa 615 - Is It A Tree?
题目:给你一些有向边(端点,长度为1),判断给定的图是否是一棵树。
分析:图论,并查集。树是一个所有点都连接的有向无环图(不连接的是森林)。
按照树的定义判断是否有环即可,有环分成两种:
1.链状环;2.存在节点有多个父亲节点;
这两种情况,只要用并查集在合并前判断是否数以一个集合即可,
如果在统一集合中,这条边一定形成环;
注意判断不能是森林。
说明:╮(╯▽╰)╭又是一个没有数据范围的题目。
#include <iostream> #include <cstdlib> #include <cstdio> using namespace std; int used[100001]; int sets[100001],rank[100001]; int set_root(int a) { if (a != sets[a]) sets[a] = set_root(sets[a]); return sets[a]; } int main() { int a,b,t = 1; while (~scanf("%d%d",&a,&b) && a >= 0 && b >= 0) { for (int i = 0 ; i < 100000 ; ++ i) { sets[i] = i; used[i] = rank[i] = 0; } int flag = 1; while (a||b) { if (set_root(a) == set_root(b)) flag = 0; if (flag) { used[a] = used[b] = 1; sets[set_root(b)] = set_root(a); } scanf("%d%d",&a,&b); } if (flag == 1) { int count = 0; for (int i = 0 ; i < 100000 ; ++ i) if (used[i] && set_root(i) == i) if (count ++) { flag = 0; break; } } if (flag == 0) printf("Case %d is not a tree.\n",t ++); else printf("Case %d is a tree.\n",t ++); } return 0; }
UVa 615 - Is It A Tree?
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。