程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> hdu1829 A Bug's Life(並查集)

hdu1829 A Bug's Life(並查集)

編輯:關於C++
開兩個並查集,然後合並的時候要合並兩次,這樣在合並之前判斷是否沖突,如果不沖突就進行合並,否則不需要繼續合並。
#include
#include
#include
#include
using namespace std;
const int MAX=2000;
int pre[2*MAX+5];
bool mark;
void init(int n){
    int i;
    for(i=1;i<=MAX+n;i++) pre[i]=i;
    mark=true;
}
int root(int x){
    if(x!=pre[x]){
        pre[x]=root(pre[x]);
    }
    return pre[x];
}
void merge(int x,int y){
    int fx,fy;
    fx=root(x);
    fy=root(y-MAX);
    if(fx==fy) {
        mark=false;
        return;
    }
    fy=root(y);
    if(fx!=fy){
        pre[fx]=pre[fy];
    }
}
int main()
{
    int t,i,n,m,x,y,k;
    scanf("%d",&t);
    for(i=1;i<=t;i++){
        scanf("%d%d",&n,&m);
        init(n);
        for(k=1;k<=m;k++){
            scanf("%d%d",&x,&y);
            if(mark){
                merge(x,y+MAX);
                merge(y,x+MAX);
            }
        }
       printf("Scenario #%d:\n",i);
        if(mark){
            printf("No suspicious bugs found!\n");
        }else{
            printf("Suspicious bugs found!\n");
        }
        printf("\n");
    }
    return 0;
}


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