题目大意：给出一个图，注意这是个有向图（小希希望任意两个房间有且仅有一条路径可以相通（除非走了回头路）），由于这个错误调试了一上午
解决：与poj 1308 一模一样，用并查集判断图的连通性，统计结点和边的个数来判断是否有回路
#include <iostream>
#include <set>
#include <utility>
using namespace std;
int num[100005];
bool mark[100005];
int Max;
set<pair<int,int> > s;
int find(int x)
{
int t=x,a;
while(num[t]>0)t=num[t];
for(int i=x;num[i]>0; i=num[a])
{
a=i;
num[i]=t;
}
return t;
}
void merge(int a,int b)
{
int fa=find(a);
int fb=find(b);
if(fa==fb)return ;
int t=num[fa]+num[fb];
if(num[fa]>num[fb]){num[fa]=fb;num[fb]=t;}
else {num[fb]=fa;num[fa]=t;}
}
void init()
{
Max=-1;
s.clear();
memset(num,-1,sizeof(num));
memset(mark,0,sizeof(mark));
}
int main()
{
int a,b,cnt=0,edge=0,vex=0;
init();
while(scanf("%d%d",&a,&b),a>=0 && b>=0)
{
if(a==0 && b==0)
{
for(int i=1;i<=Max && cnt!=2;i++)
{
if( mark[i] )
{
vex++;
if(num[i]<0)cnt++;
}
}
edge=s.size();
//判断0 0的情况
if(cnt==0 && vex==0 && edge==0){printf("Yes\n");continue;}
if(cnt==1 && edge==vex-1)printf("Yes\n");
else printf("No\n");
cnt=0;
edge=0;
vex=0;
init();
continue;
}
if(a!=b)
{
s.insert(make_pair(b,a));
merge(a,b);
}
if(a>Max)Max=a;
if(b>Max)Max=b;
mark[a]=mark[b]=true;
}
// system("pause");
return 0;
}