程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU1272小希的迷宮 並查集確定圖為樹

HDU1272小希的迷宮 並查集確定圖為樹

編輯:C++入門知識

這題主要是解決一個圖是否是樹的問題。
有很多細節需要注意。
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; 

 

 
 

作者:Lulipeng_cpp

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved