易旅游网站建设,网站服务器天付,邢台哪有学做网站的,移动关闭流量自动续费判断一个图是不是树
问题描述
给一个以0 0结尾的整数对列表#xff0c;除0 0外的每两个整数表示一条连接了这两个节点的边。假设节点编号不超过100000大于0。你只要判断由这些节点和边构成的图是不是树。是输出YES#xff0c;不是输出NO。 输入样例1
6 8 5 3 5 2 6 4 5…判断一个图是不是树
问题描述
给一个以0 0结尾的整数对列表除0 0外的每两个整数表示一条连接了这两个节点的边。假设节点编号不超过100000大于0。你只要判断由这些节点和边构成的图是不是树。是输出YES不是输出NO。 输入样例1
6 8 5 3 5 2 6 4 5 6 0 0输出样例1
YES输入样例2
8 1 7 3 6 2 8 9 7 5 7 4 7 8 7 6 0 0输出样例2
YES输入样例3
3 8 6 8 6 4 5 3 5 6 5 2 0 0输出样例3
NO输入样例4
1 2 3 4 0 0输出样例4
NO输入样例5
空树也是树
0 0输出样例5
YESc代码
#includebits/stdc.h
#includestdio.husing namespace std;int a, b, cont 0;
int arr[100001];
bool key true;
unordered_setint st;int myfind(int x) {int root x;while(root ! arr[root]) root arr[root];int i x, j;while(i ! root) {j arr[i];arr[i] root;i j;}return root;
}void mymerge(int x, int y) {x myfind(x), y myfind(y);if (x ! y) arr[y] arr[x];
}int main() {for (int i 1; i 100000; i) arr[i] i;while(true) {scanf(%d %d, a, b);if (a 0 b 0) {if (cont 0) {printf(YES\n);return 0;}if (key st.size() ! cont 1) key false;if (key) {int root -1;for (int x : st) {int k myfind(x);if (root -1) root k;if (k ! root) {key false;break;}}}if (key) printf(YES\n);else printf(NO\n);break;}else {cont;if (st.find(a) st.end()) st.insert(a);if (st.find(b) st.end()) st.insert(b);if (key) {int x myfind(a), y myfind(b);if (x y) key false;else mymerge(a, b);}}}return 0;
}算法解析
满足下面三个条件的图是树
1、不存在环。
2、所有点都是互相连通的。
3、点数边数 1。
判断环
用并查集给每个点一个初始的编号并初始化所有节点的父亲为本身。每新加入一条边就把边相连的两个集合合并到一起如果边相连的集合原本就是同一个说明已经成环不是生成树。
int x myfind(a), y myfind(b);
if (x y) key false; //边相连的集合原本就是同一个说明已经成环不是生成树。
else mymerge(a, b); //否则合并一下判断节点数和边数的关系
把点存在一个unordered_set里面就行因为不能存重复的边用一个cont就可以存
cont;
if (st.find(a) st.end()) st.insert(a);
if (st.find(b) st.end()) st.insert(b);
......
if (key st.size() ! cont 1) key false;判断连通性
如果是连通的根据我们之前的合并操作每一个节点应该都属于同一个集合如果不是则不是树。
int root -1;
for (int x : st) {int k myfind(x);if (root -1) root k;if (k ! root) {key false;break;}
}
