程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj2236和poj1611並查集問題

poj2236和poj1611並查集問題

編輯:C++入門知識

poj2236和poj1611並查集問題


  

問在計算機壞了,修復若干,問檢測兩台是否能連通

 

 

#include 
#include 
#include 

using namespace std;
const int N = 1005;

struct Point
{
    int x,y;
};

Point p[N];
int repaired[N];
int pre[N],rank[N];

int dist(Point A,Point B)
{
    return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);
}

void Init(int n)
{
    for(int i=1;i<=n;i++)
    {
        pre[i] = i;
        rank[i] = 1;
    }
}

int Find(int x)
{
    if(pre[x] != x)
        pre[x] = Find(pre[x]);
    return pre[x];
}

void Union(int x,int y)
{
    x = Find(x);
    y = Find(y);
    if(x == y) return;
    if(rank[x] >= rank[y])
    {
        pre[y] = x;
        rank[x] += rank[y];
    }
    else
    {
        pre[x] = y;
        rank[y] += rank[x];
    }
}

int main()
{
    char ch[5];
    int n,d,x,y;
    scanf(%d%d,&n,&d);
    for(int i=1;i<=n;i++)
        scanf(%d%d,&p[i].x,&p[i].y);
    int cnt = 0;
    Init(n);
    while(~scanf(%s,ch))
    {
        if(ch[0] == 'O')
        {
            scanf(%d,&x);
            for(int i=0;i

 

 

poj1611問是:學生0感染病毒,跟他一組的都得病,他可以交叉加入若干組,問一共的病的人數

 

 

並查集合並後,遍歷查詢是否同一集合即可

 

 

#include 
#include 
#include 
using namespace std;
const int MAX = 30010;
int M,N;
typedef struct UF
{
	int par[MAX],rank[MAX];
	void init(){
		for (int i = 0; i <= MAX; ++i)
		{
			par[i]=i;
			rank[i]=1;
		}
	};
	int find(int x){
		if(x!=par[x]){
			par[x]=find(par[x]);
		};
		return par[x];
	};
	int same(int x,int y){
		return find(x)==find(y);
	};
	void unions(int x,int y){
		int xx=find(x);
		int yy=find(y);
		if (xx==yy)
		{
			return ;
		}
		if (rank[xx]=rank[yy])
		{
			par[yy]=xx;
			rank[xx]+=rank[yy];
		}
	};
}UF;
UF uf;
int main(int argc, char const *argv[])
{
	while(scanf(%d%d,&N,&M)&&M&&N){
		uf.init();
		for (int i = 0; i < M; ++i)
		{
			int num,fir;
			scanf(%d,&num);
			scanf(%d,&fir);
			for (int j = 1; j < num ; ++j)
			{
				int tmp;
				scanf(%d,&tmp);
				uf.unions(fir,tmp);
			}
		}
		int sum=1;
		for (int i = 1; i < N; ++i)
		{
			if (uf.same(0,i))
			{
				sum++;
			}
		}
		printf(%d
,sum);
	}
	return 0;
}


 

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