信誉好的专业网站建设,产品详情页模板免费下载,百度站长管理平台,湖北网站开发公司// 题意: 给出一些边#xff0c;由所给出的边能否构成一棵树.#xff08;节点数100#xff09;// 思路: n个顶点的树具有3个特点:连通,不含环,恰好包含n-1条边.只要有任意两个,就能推导出第3个// 所以我们可以通过是否连通和不含环来判断可以构成树.// 不含环: 通过并查… // 题意: 给出一些边由所给出的边能否构成一棵树.节点数100// 思路: n个顶点的树具有3个特点:连通,不含环,恰好包含n-1条边.只要有任意两个,就能推导出第3个// 所以我们可以通过是否连通和不含环来判断可以构成树.// 不含环: 通过并查集,如果边a-b, a和b的祖先结点都一样,则是有环,包括a-a和 a-b 重复出现// 连通: 只有一个根结点#include iostream //并查集using namespace std;#define maxn 1000int p[maxn],isNode[maxn];int find(int x){return p[x]x ? x : p[x]find(p[x]);}int main(){int t1,a,b;while(cinaba!-1) // a-b {if(a0) //只有 0 0 ,空树也是一棵树 { printf(Case %d is a tree.\n,t);continue; }for(int i1;imaxn;i) { p[i]i; isNode[i]0; }int isTree1,tail0;while(a!0) {if(isTree) {int xfind(a),yfind(b);if(xy) //说明存在环 { isTree0; }else { p[y]x; //a-b isNode[a]isNode[b]1; //标志结点 tailmax(tail,max(a,b)); //结点的下标并不是顺序增加 1 } } cinab; }if(!isTree) printf(Case %d is not a tree.\n,t);else {int roots0;for(int i1;itail;i) {if(isNode[i]p[i]i) //找到一根结点 { roots;if(roots1)break; } }if(roots1) printf(Case %d is a tree.\n,t);else printf(Case %d is not a tree.\n,t); //没有根结点或者不只一个根结点 } }return 0;} 转载于:https://www.cnblogs.com/mjc467621163/archive/2011/07/20/2112182.html
