题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1272
复制代码
#include<iostream>
using namespace std;
const int MAX_VETEX_NUM = 100001;
bool flag[MAX_VETEX_NUM];
int connectedList[MAX_VETEX_NUM];
bool isOk = true;
int nStart,nEnd;
void initConnectedList()
{
for (int i = 0; i < MAX_VETEX_NUM; ++i)
{
connectedList[i] = i;
flag[i] = false;
}
}
int findInConnectList(int vetex)
{
int pos = vetex;
while(pos != connectedList[pos])
{
pos = connectedList[pos];
}
return pos;
}
int countListNum()
{
int count = 0;
for (int i = 0; i < MAX_VETEX_NUM; ++i)
{
if (flag[i] == true)
{
if (findInConnectList(i) == i)
{
++count;
}
}
}
return count;
}
void process()
{
if( findInConnectList(nStart) == findInConnectList(nEnd))
{
isOk = false;
return;
}
if( findInConnectList(nStart) == nStart && findInConnectList(nEnd) == nEnd)
{
connectedList[nEnd] = nStart;
}
else if(findInConnectList(nStart) == nStart)
{
connectedList[nStart] = findInConnectList(nEnd);
}
else
{
connectedList[nEnd] = findInConnectList(nStart);
}
flag[nStart] = true;
flag[nEnd] = true;
}
int main()
{
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) // 如果没有回环,也有可能在不同连通分量中
{
int count = 0;
count = countListNum();
if(count>1)
{
isOk = false;
}
}
}
else
{
isOk = true;
}
if(isOk == false)
{
cout << "No" << endl;
}
else
{
cout << "Yes" << endl;
}
}
return 0;
}
复制代码
本文转自Phinecos(洞庭散人)博客园博客，原文链接：http://www.cnblogs.com/phinecos/archive/2009/09/15/1567216.html，如需转载请自行联系原作者
