题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1272
<!--<br /><br />Code highlighting produced by Actipro CodeHighlighter (freeware)<br />http://www.CodeHighlighter.com/<br /><br />-->#include<iostream>
usingnamespacestd;
constintMAX_VETEX_NUM=100001;
boolflag[MAX_VETEX_NUM];
intconnectedList[MAX_VETEX_NUM];
boolisOk=true;
intnStart,nEnd;
voidinitConnectedList()
{
for(inti=0;i<MAX_VETEX_NUM;++i)
{
connectedList[i]=i;
flag[i]=false;
}
}
intfindInConnectList(intvetex)
{
intpos=vetex;
while(pos!=connectedList[pos])
{
pos=connectedList[pos];
}
returnpos;
}
intcountListNum()
{
intcount=0;
for(inti=0;i<MAX_VETEX_NUM;++i)
{
if(flag[i]==true)
{
if(findInConnectList(i)==i)
{
++count;
}
}
}
returncount;
}
voidprocess()
{
if(findInConnectList(nStart)==findInConnectList(nEnd))
{
isOk=false;
return;
}
if(findInConnectList(nStart)==nStart&&findInConnectList(nEnd)==nEnd)
{
connectedList[nEnd]=nStart;
}
elseif(findInConnectList(nStart)==nStart)
{
connectedList[nStart]=findInConnectList(nEnd);
}
else
{
connectedList[nEnd]=findInConnectList(nStart);
}
flag[nStart]=true;
flag[nEnd]=true;
}
intmain()
{
while(cin>>nStart>>nEnd)
{
if(nStart==-1&&nEnd==-1)break;
if(nStart||nEnd)
{
isOk=true;
memset(flag,false,sizeof(flag));
initConnectedList();
process();
while(cin>>nStart>>nEnd,nStart||nEnd)
{
if(isOk==true)
{
process();
}
}
if(isOk==true)//如果没有回环,也有可能在不同连通分量中
{
intcount=0;
count=countListNum();
if(count>1)
{
isOk=false;
}
}
}
else
{
isOk=true;
}
if(isOk==false)
{
cout<<"No"<<endl;
}
else
{
cout<<"Yes"<<endl;
}
}
return0;
}
分享到:
相关推荐
标题这几题都是去判断树的,只是输出不一样 要用定义去做树,那肯定要知道树是什么 学习的时候很迷茫是没搞清楚大方向 什么是大方向呢? 两个字:图论 树肯定是图,但图不一定是树 搞清楚这么几个知识点就可以愉快的...
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
HDU的一题........HDU DP动态规
hdu 1574 passed sorce
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
HDU最全ac代码
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
hdu动态规划算法集锦
hdu 1166线段树代码
算法-迷宫城堡(HDU-1269)(包含源程序).rar
hdu题目分类
HDU图论题目分类