`
dato0123
  • 浏览: 906474 次
文章分类
社区版块
存档分类
最新评论

HDU1272 小希的迷宫

 
阅读更多
题目链接: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;
}
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics