HDU 1213 How many tables? 并查集/DFS

• 題目

• 題意

今天是Ignatius的生日，他邀請了許多朋友。現在是吃晚飯的時間，Ignatius想知道他至少需要準備多少桌。必須注意的是，并非所有的朋友都互相認識對方，有的人不願意和陌生人坐在一桌。針對此問題的一個重要的規則是，如果我告訴你A知道B，B知道C，這意味着，A和C認識對方，這樣他們就可以留在一個桌子。但是如果我告訴你，A知道B，B知道C，D知道E，那麼ABC可以坐在一起，DE就得另外再坐一桌了。你的任務是請根據輸入的朋友之間的關系，幫助Ignatius

 求出需要安排多少桌。

很明顯的并查集的題目。

有幾個并查集，就安排多少桌。

十分偏執地想用DFS寫，用了二維數組就一直debug不出來，還是看了别人的代碼。判斷連通性，判環什麼的，都是一維數組。

判斷圖的連通性（DFS BFS 并查集）

• 并查集的實作

之前一直不喜歡遞歸的find()來尋找父節點，結果這次用遞歸寫，就MLE了。

又改回了while循環。仍舊是大腦短路的一次while。

在路徑壓縮過程中，主要思想在于，從葉子節點到父節點中，經過的每個結點，都要讓他們的pre等于r（根）.

但是不能直接 pre[i] = r，而是得先記錄一下pre[i]的目前數值，防止找不到鍊子。。。。

//HDU 1213 
#include<iostream>
#include<algorithm>
#include<set>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<stdio.h>
using namespace std;
#define ll long long

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

int find(int x)
{
	int r=x;
	while(r!=pre[r])
	{
		r=pre[r];
	}
	int j=x;
	while(j!=r)//一條路上全部的節點指派為r 
	{
		int t=pre[j];
		pre[j]=r;
		j=t;
	}
	return r;
}

int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		scanf("%d%d",&n,&m);
		Init();
		for(int i=1;i<=m;i++)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			int x=find(a);
			int y=find(b);
			if(x!=y)
			{
				pre[x]=y;//pre[a]=b的 挖槽，真香 
			}
		}
		int cnt=0;
		for(int i=1;i<=n;i++)
			if(pre[i]==i) cnt++;
		cout<<cnt<<endl;
		
	}
}
           

如果根節點不同，指派容易出錯啊。。。。 

• DFS的實作

vis[ i ]數組表示，第 i 個節點有沒有被通路，有沒有連接配接到之前的連通圖（并查集）中。

#include<iostream>
#include<algorithm>
#include<set>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<stdio.h>
using namespace std;
#define ll long long
int mp[1005][1005];
int vis[1005];//1-i 是否已經連上 
int m,n;
int cnt=1;
int countpoint=0;
int dfs(int x)
{
	if(vis[x]) return 0; //順便記憶化搜尋一下 
	vis[x]=true;
	for(int j=1;j<=n;j++)
	{
		if(mp[x][j] && vis[j]==false)
		{
			dfs(j);
		}
	 } 
}

int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		scanf("%d%d",&n,&m);
		memset(mp,0 ,sizeof(mp));
		memset(vis,0,sizeof(vis));
		
		for(int i=1;i<=m;i++)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			mp[a][b]=true;
			mp[b][a]=true;
			mp[i][i]=true;
		}
	
		int cnt=0;
		for(int i=1;i<=n;i++)
		{
			if(vis[i]==false) 
			{
				dfs(i);
				cnt++;
			}
		}
		cout<<cnt<<endl;
	}
}
           

這個最後的數個數，跟 滑雪 那道題，蜜汁相似