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

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

【题目描述】

在这里插入图片描述

【深搜（邻接矩阵）】

#include<bits/stdc++.h>
using namespace std;
int G[1010][1010],v[1010];
int n,x,y,s,ans=-0x7ffffff;
void dfs(int x)
{for (int i=1;i<=n;i++)if (G[x][i]&&!v[i])v[i]=1,s++,dfs(i);
}
int main()
{cin>>n;cin>>x>>y;while (x&&y){G[x][y]=1,G[y][x]=1;cin>>x>>y;}for (int i=1;i<=n;i++)if (!v[i]){v[i]=1,s=1;dfs(i);ans=max(s,ans);}cout<<ans;return 0;	
}

【深搜（邻接表）】

#include<bits/stdc++.h>
using namespace std;
struct note{int y,next;
}e[1100];
int head[1100],v[1100];
int n,tot,x,y,s,ans=-0x7ffffff;
void dfs(int x)
{v[x]=1;for (int i=head[x];i;i=e[i].next)if (!v[e[i].y])s++,dfs(e[i].y);
}
int main()
{cin>>n;cin>>x>>y;while (x&&y){e[++tot]=(note){y,head[x]},head[x]=tot;e[++tot]=(note){x,head[y]},head[y]=tot;cin>>x>>y;}for (int i=1;i<=n;i++)if (!v[i]){v[i]=1,s=1;dfs(i);ans=max(s,ans);}cout<<ans;return 0;	
}

【广搜（邻接矩阵）】

#include<bits/stdc++.h>
using namespace std;
int G[1010][1010],q[1100],v[1010];
int n,zz,h,t,x,y,s,ans=-0x7ffffff;
void bfs(int x)
{s=h=1,t=0;q[++t]=x,v[x]=1;while(h<=t){zz=q[h],h++;for (int i=1;i<=n;i++)if (G[zz][i]&&!v[i]){s++,v[i]=1;q[++t]=i;}}
}
int main()
{cin>>n;cin>>x>>y;while (x&&y){G[x][y]=1,G[y][x]=1;cin>>x>>y;}for (int i=1;i<=n;i++)if (!v[i]){memset(q,0,sizeof(q));v[i]=1,s=1;bfs(i);ans=max(s,ans);}cout<<ans;return 0;	
}

【广搜（邻接表）】

#include<bits/stdc++.h>
using namespace std;
struct note
{int y,next;
} e[1100];
int head[1100],v[1100],q[1100];
int h,t,n,zz,tot,x,y,s,ans=-0x7ffffff;
void bfs(int x)
{s=h=1,t=0;q[++t]=x,v[x]=1;while(h<=t){zz=q[h],h++;for (int i=head[zz];i;i=e[i].next)if (!v[e[i].y]){s++,v[e[i].y]=1;q[++t]=e[i].y;}}
}
int main()
{cin>>n;cin>>x>>y;while (x&&y){e[++tot]=(note){y,head[x]},head[x]=tot;e[++tot]=(note){x,head[y]},head[y]=tot;cin>>x>>y;}for (int i=1;i<=n;i++)if (!v[i]){memset(q,0,sizeof(q));bfs(i);ans=max(s,ans);}cout<<ans;return 0;	
}

【广搜（邻接表+STL）】

#include<bits/stdc++.h>
using namespace std;
struct note{int y,next;
}e[1100];
int head[1100],v[1100];
int n,zz,tot,x,y,s,ans=-0x7ffffff;
queue<int> q;
void bfs(int x)
{q.push(x);s=v[x]=1;while(!q.empty()){zz=q.front();q.pop();for (int i=head[zz];i;i=e[i].next)if (!v[e[i].y]){s++,v[e[i].y]=1;q.push(e[i].y);}}
}
int main()
{cin>>n;cin>>x>>y;while (x&&y){e[++tot]=(note){y,head[x]},head[x]=tot;e[++tot]=(note){x,head[y]},head[y]=tot;cin>>x>>y;}for (int i=1;i<=n;i++)if (!v[i]){v[i]=1,s=1;bfs(i);ans=max(s,ans);}cout<<ans;return 0;	
}

【深搜动态数组】

#include<bits/stdc++.h>
using namespace std;
int v[1010];
int n,x,y,s,ans=-0x7ffffff;
vector<int> G[1010];
void dfs(int x)
{for (int i=0;i<G[x].size();i++){y=G[x][i];if (!v[y]){v[y]=1,s++;dfs(y);}}}
int main()
{cin>>n;cin>>x>>y;while (x&&y){G[x].push_back(y);G[y].push_back(x);cin>>x>>y;}for (int i=1;i<=n;i++)if (!v[i]){s=v[i]=1,dfs(i);ans=max(s,ans);}cout<<ans;return 0;	
}

【广搜动态数组】

#include<bits/stdc++.h>
using namespace std;
int v[1010];
int n,zz,x,y,s,ans=-0x7ffffff;
vector<int> G[1010];
queue<int> q;
void bfs(int x)
{q.push(x);v[x]=1;while(!q.empty()){zz=q.front(),q.pop();for (int i=0;i<G[zz].size();i++){y=G[zz][i];if (!v[y]){s++,v[y]=1;q.push(y);}}}
}
int main()
{cin>>n;cin>>x>>y; while (x&&y){G[y].push_back(x);G[x].push_back(y);cin>>x>>y;}for (int i=1;i<=n;i++)if (!v[i]){v[i]=s=1;bfs(i);ans=max(s,ans);}cout<<ans;return 0;	
}