【并查集】求连通块的两种方法（DFS，并查集）

问题：给一个图，图中有n个顶点，m条边，求图中连通块的个数。

以下有两种方法可用：1.DFS 2.并查集

1.用邻接矩阵存图，dfs找连通块数

.#include<bits/stdc++.h> const int N=1005; using namespace std; vector<int> t[N]; int vis[N]={0}; void dfs(int k) { for(int i=0;i<t[k].size();i++) { if(vis[t[k][i]]==0) { vis[t[k][i]]=1; dfs(t[k][i]); } } } int main() { int n,m;//n个顶点，m条边 cin>>n>>m; int a,b;//边所连接的两个顶点 for(int i=1;i<=m;i++) { cin>>a>>b; t[a].push_back(b); t[b].push_back(a); } int ans=0;//记录连通块数量 for(int i=1;i<=n;i++) { if(vis[i]==0) { vis[i]=1; dfs(i); ans++; } } cout<<ans<<endl; return 0; }

2.并查集思想，每个顶点找其父节点（find函数），若父节点相同，则属于同一个连通块。

#include<bits/stdc++.h> using namespace std; const int N=1005; int n,m; vector<int> t[N]; int pre[N],root[N];

void init(int nn) { for(int i=1;i<=nn;i++) pre[i]=i; } int find(int x) { int f=x; while(x!=pre[x])//找到x的父节点 x=pre[x];

int j; while(f!=pre[f])//依次将x上面的节点的父节点赋为x; { j=f; f= pre[f]; pre[j]=x; } return x; }

void merge(int a,int b) { int t1,t2; t1=find(a); t2=find(b); if(t1!=t2) { pre[t2]=t1; } }

int block(int nn) { int ans=0; for(int i=1;i<=nn;i++) root[pre[i]]=1; for(int i=1;i<=nn;i++) ans+=root[i]; return ans; } int main() { scanf("%d%d",&n,&m); int a,b;//边所连接的两个顶点 init(n); for(int i=1;i<=m;i++) { scanf("%d%d",&a,&b); t[a].push_back(b); t[b].push_back(a); merge(a,b); } printf("%d",block(n)); return 0; }