首页 > 代码库 > POJ1308
POJ1308
1、题目链接地址
http://poj.org/problem?id=1308
2、源代码
#include<iostream>using namespace std;#define MAXN 100int set[MAXN]; //set[]记录每个节点的父节点int FindSet(int x) //寻找x所在根的根节点{ if(set[x]==x) return x; if(set[x]==-x) return -x; else set[x]=FindSet(set[x]); return set[x];}int main(){ int pointa,pointb,FSa,FSb; int cas=1,num=0,I; bool judge=0,flag=0;//judge为是否判断完,flag为是否有边输入 for(I=0;I<MAXN;I++) set[I]=-I; while(cin>>pointa>>pointb,pointa>=0) { if(pointa==0) { if(num==1||flag==0) cout<<"Case "<<cas<<" is a tree.\n"; else cout<<"Case "<<cas<<" is not a tree.\n"; cas++; flag=0; num=0; judge=0; for(I=0;I<MAXN;I++) set[I]=-I; } else { flag=1; //有边 FSa=FindSet(pointa); if(FSa==-pointa) set[pointa]=pointa; FSb=FindSet(pointb); if(FSb==-pointb) set[pointb]=pointb; if(FSa==FSb) { num=0; judge=1; } if(judge==0) { if(FSb==pointb) //pontb是已出现过的根节点 { if(FSa!=-pointa) //当pointa不是还没有出现过的点 { num--; } set[pointb]=FindSet(pointa); } else { if(FSb==-pointb) //pointb还没有出现过 { if(FSa==-pointa) //pointa还没有出现过 { num++; } set[pointb]=FindSet(pointa); } else { num=0; judge=1; } } } } } return 0;}
好久的东西,粗略整理一下。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。