SSL 1759 连通分量（七种做法）

本文主要是介绍SSL 1759 连通分量（七种做法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：

在这里插入图片描述

解题思路：

首先需要有前置知识，在无向图中，联通分量表示最大联通子图中的节点个数。
然后我们考虑多种做法。

做法一： $d f s +$ 邻接矩阵

#include <iostream>
#include <cstring>
using namespace std;
int n,g[1001][1001]={0},sum;
bool vis[100010]={false};
int dfs(int x)
{vis[x]=true;for(int i=1;i<=n;i++)if(!vis[i]&&g[x][i])sum++,dfs(i);return sum;
} 
int main()
{cin>>n;int x,y;cin>>x>>y;while(x&&y){g[x][y]=1;g[y][x]=1;cin>>x>>y;}int ans=0;for(int i=1;i<=n;i++){sum=1;if(vis[i]) continue;ans=max(ans,dfs(i));}cout<<ans;return 0;
}

做法二： $d f s +$ 链式前向星

#include <iostream>
#include <cstring>
using namespace std;
int n,sum,tot=0;
int head[100010]={0};
struct node
{int y,next;
} e[100010];
bool vis[100010]={false};
int dfs(int x)
{vis[x]=true;for(int i=head[x];i;i=e[i].next)if(!vis[e[i].y])sum++,dfs(e[i].y);return sum;
} 
int main()
{cin>>n;int x,y;cin>>x>>y;while(x&&y){tot++;e[tot]=(node){y,head[x]},head[x]=tot;tot++;e[tot]=(node){x,head[y]},head[y]=tot;cin>>x>>y;}int ans=0;for(int i=1;i<=n;i++){sum=1;if(vis[i]) continue;ans=max(ans,dfs(i));}cout<<ans;return 0;
}

做法三： $d f s +$ 邻接表（vector）

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
int n,sum;
vector<int> g[100010];
bool vis[100010]={false};
int dfs(int x)
{vis[x]=true;for(int i=0;i<g[x].size();i++)if(!vis[g[x][i]])sum++,dfs(g[x][i]);return sum;
} 
int main()
{cin>>n;int x,y;cin>>x>>y;while(x&&y){g[x].push_back(y);g[y].push_back(x);cin>>x>>y;}int ans=0;for(int i=1;i<=n;i++){sum=1;if(vis[i]) continue;ans=max(ans,dfs(i));}cout<<ans;return 0;
}

做法四： $b f s +$ 邻接矩阵

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
int n,sum;
int g[1001][1001]={0};
int q[100010]={0},h=1,t=1;
bool vis[100010]={false};
int bfs(int x)
{vis[x]=true;q[t]=x;t++;while(h<t){int u=q[h];h++;for(int i=1;i<=n;i++)if(!vis[i]&&g[u][i]==1)sum++,vis[i]=true,q[t]=i,t++;}return sum;
} 
int main()
{cin>>n;int x,y;cin>>x>>y;while(x&&y){g[x][y]=1;g[y][x]=1;cin>>x>>y;}int ans=0;for(int i=1;i<=n;i++){sum=1;if(vis[i]) continue;ans=max(ans,bfs(i));}cout<<ans;return 0;
}

做法五： $b f s +$ 链式前向星

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
int n,sum;
int head[100010]={0},tot=0;
struct node
{int y,next;
} e[100010];
int q[100010]={0},h=1,t=1;
bool vis[100010]={false};
int bfs(int x)
{vis[x]=true;q[t]=x;t++;while(h<t){int u=q[h];h++;for(int i=head[u];i;i=e[i].next)if(!vis[e[i].y])sum++,vis[e[i].y]=true,q[t]=e[i].y,t++;}return sum;
} 
int main()
{cin>>n;int x,y;cin>>x>>y;while(x&&y){tot++;e[tot]=(node){y,head[x]},head[x]=tot;tot++;e[tot]=(node){x,head[y]},head[y]=tot;cin>>x>>y;}int ans=0;for(int i=1;i<=n;i++){sum=1;if(vis[i]) continue;ans=max(ans,bfs(i));}cout<<ans;return 0;
}

做法六： $b f s +$ 邻接表

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
int n,sum;
int q[100010]={0},h=1,t=1; 
vector<int> g[100010];
bool vis[100010]={false};
int bfs(int x)
{vis[x]=true;q[t]=x;t++;while(h<t){int u=q[h];h++;for(int i=0;i<g[u].size();i++)if(!vis[g[u][i]])sum++,vis[g[u][i]]=true,q[t]=g[u][i],t++;}return sum;
} 
int main()
{cin>>n;int x,y;cin>>x>>y;while(x&&y){g[x].push_back(y);g[y].push_back(x);cin>>x>>y;}int ans=0;for(int i=1;i<=n;i++){sum=1;if(vis[i]) continue;ans=max(ans,bfs(i));}cout<<ans;return 0;
}

做法七： $b f s +$ 邻接表 $+$ queue

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
int n,sum;
queue<int> q;
vector<int> g[100010];
bool vis[100010]={false};
int bfs(int x)
{vis[x]=true;q.push(x);while(!q.empty()){int u=q.front();q.pop();for(int i=0;i<g[u].size();i++)if(!vis[g[u][i]])sum++,vis[g[u][i]]=true,q.push(g[u][i]);}return sum;
} 
int main()
{cin>>n;int x,y;cin>>x>>y;while(x&&y){g[x].push_back(y);g[y].push_back(x);cin>>x>>y;}int ans=0;for(int i=1;i<=n;i++){sum=1;if(vis[i]) continue;ans=max(ans,bfs(i));}cout<<ans;return 0;
}