這題主要是解決一個圖是否是樹的問題。
有很多細節需要注意。
1、空樹也是樹。
2、一個圖若是樹需滿足兩個條件:
①連通分量為一;
②圖中無環,包括自環和非自環。
3、邊數+1=頂點數。
AC代碼:
[cpp]
#include<iostream>
using namespace std;
const int MAX=100001;
int father[MAX];
bool flag[MAX],flagLC;
void initial() //初始化
{
for(int i=1;i<MAX;i++)
father[i]=i;
}
int find(int x) //查找
{
while(father[x]!=x)
x=father[x];
return x;
}
void combine(int a,int b) //合並
{
int tmpa=find(a);
int tmpb=find(b);
if(tmpa!=tmpb)
father[tmpa]=tmpb;
else
flagLC=true; //a,b在同一個連通分量中,說明有環
}
int main()
{
int i,a,b,connectedComponent,edgeNum,nodeNum;
bool flagCircle; //自環
while(1)
{
initial();
edgeNum=0; //邊數
flagLC=flagCircle=false; //標志是否有環
memset(flag,false,sizeof(flag)); //標志在圖內的點,在為true
scanf("%d%d",&a,&b);
if(a==0 && b==0) //空樹
{
cout<<"Yes"<<endl;
continue;
}
if(a==-1 && b==-1) break;
if(a==b) flagCircle=true;
flag[a]=true;
flag[b]=true;
edgeNum++;
combine(a,b);
while(1)
{
scanf("%d%d",&a,&b);
if(a==0 && b==0) break;
if(a==b) flagCircle=true;
flag[a]=true;
flag[b]=true;
edgeNum++;
combine(a,b);
}
connectedComponent=0; //連通分量數
nodeNum=0; //點數
for(i=1;i<MAX;i++) //判斷圖是否連通,tmp=1連通
{
if(flag[i])
{
nodeNum++; //計算圖內包含的所有點
if(father[i]==i)
connectedComponent++;
}
} www.2cto.com
if(connectedComponent==1 && nodeNum==edgeNum+1 && !flagCircle && !flagLC) //連通的無環圖為樹
cout<<"Yes";
else
cout<<"No";
cout<<endl;
}
return 0;
}