【SSL】2021.12.17 1759.求连通分量

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

快速链接

原题网址
题目描述
格式
- 输入格式
- 输出格式
样例
- 输入样例
- 输出样例
提示
解题思路
Code
- dfs
- - 邻接表
  - 邻接矩阵
  - vector
- bfs
- - 邻接表
  - 邻接表+queue
  - 邻接矩阵
  - vector

原题网址

由于某些原因，这个网址会进不去…

题目描述

求一个图的连通分量.
1759-1

格式

输入格式

一个数 $n$ 表示顶点数。
接下来每行输入空格隔开的两个数 $u, v$ ，表示 $u, v$ 之间有一条边，以 $0, 0$ 结束。

输出格式

图的连通分量。

样例

输入样例

输出样例

提示

$n\le100$

解题思路

模板题。

Code

dfs

邻接表

#include<iostream>
#include<istream>
#include<ostream>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
using namespace std;
const int maxn=100,maxm=10000;
int n,x,y,s,ans,len,l[maxn+5],v[maxn+5];
struct node {int y,next;
}nodes[maxm+5];
void dfs(int q) {v[q]=1;for(int i=l[q];i;i=nodes[i].next) {if(!v[nodes[i].y]) {s++;dfs(nodes[i].y);}}
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cin>>n>>x>>y;while(x&&y) {nodes[++len]=(node){y,l[x]};l[x]=len;nodes[++len]=(node){x,l[y]};l[y]=len;cin>>x>>y;}for(int i=1;i<=n;i++) {if(!v[i]) {v[i]=s=1;dfs(i);ans=max(ans,s);}}cout<<ans;return 0;
}

邻接矩阵

#include<iostream>
#include<istream>
#include<ostream>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
using namespace std;
const int maxn=100;
int n,x,y,s,ans,g[maxn+5][maxn+5],v[maxn+5];
void dfs(int q) {v[q]=1;for(int i=1;i<=n;i++) {if(!v[i]&&g[q][i]) {s++;dfs(i);}}
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cin>>n>>x>>y;while(x&&y) {g[x][y]=g[y][x]=1;cin>>x>>y;}for(int i=1;i<=n;i++) {if(!v[i]) {v[i]=s=1;dfs(i);ans=max(ans,s);}}cout<<ans;return 0;
}

vector

#include<iostream>
#include<istream>
#include<ostream>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
using namespace std;
const int maxn=100;
int n,x,y,s,ans,v[maxn+5];
vector<int> g[maxn+5];
void dfs(int q) {v[q]=1;for(int i=0;i<g[q].size();i++) {int j=g[q][i];if(!v[j]) {s++;dfs(j);}}
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cin>>n>>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]) {v[i]=s=1;dfs(i);ans=max(ans,s);}}cout<<ans;return 0;
}

bfs

邻接表

#include<iostream>
#include<istream>
#include<ostream>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
using namespace std;
const int maxn=100,maxm=10000;
int n,x,y,s,ans,len,l[maxn+5],v[maxn+5];
struct node {int y,next;
}nodes[maxm+5];
void bfs(int q) {int head=0,tail=1,state[maxn+5];state[1]=q;do {head++;for(int i=l[state[head]];i;i=nodes[i].next) {if(!v[nodes[i].y]) {v[nodes[i].y]=1;s++;state[++tail]=nodes[i].y;}}}while(head<tail);
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cin>>n>>x>>y;while(x&&y) {nodes[++len]=(node){y,l[x]};l[x]=len;nodes[++len]=(node){x,l[y]};l[y]=len;cin>>x>>y;}for(int i=1;i<=n;i++) {if(!v[i]) {v[i]=s=1;bfs(i);ans=max(ans,s);}}cout<<ans;return 0;
}

邻接表+queue

#include<iostream>
#include<istream>
#include<ostream>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
using namespace std;
const int maxn=100,maxm=10000;
int n,x,y,s,ans,len,l[maxn+5],v[maxn+5];
struct node {int y,next;
}nodes[maxm+5];
void bfs(int q) {int head=0,tail=1;queue<int>state;state.push(q);while(state.size()){int w=state.front();state.pop();for(int i=l[w];i;i=nodes[i].next) {if(!v[nodes[i].y]) {v[nodes[i].y]=1;s++;state.push(nodes[i].y);}}}
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cin>>n>>x>>y;while(x&&y) {nodes[++len]=(node){y,l[x]};l[x]=len;nodes[++len]=(node){x,l[y]};l[y]=len;cin>>x>>y;}for(int i=1;i<=n;i++) {if(!v[i]) {v[i]=s=1;bfs(i);ans=max(ans,s);}}cout<<ans;return 0;
}

邻接矩阵

#include<iostream>
#include<istream>
#include<ostream>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
using namespace std;
const int maxn=100;
int n,x,y,s,ans,g[maxn+5][maxn+5],v[maxn+5];
void bfs(int q) {int head=0,tail=1,state[maxn+5];state[1]=q;do {head++;for(int i=1;i<=n;i++) {if(g[state[head]][i]&&!v[i]) {v[i]=1;s++;state[++tail]=i;}}}while(head<tail);
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cin>>n>>x>>y;while(x&&y) {g[x][y]=g[y][x]=1;cin>>x>>y;}for(int i=1;i<=n;i++) {if(!v[i]) {v[i]=s=1;bfs(i);ans=max(ans,s);}}cout<<ans;return 0;
}

vector

#include<iostream>
#include<istream>
#include<ostream>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
using namespace std;
const int maxn=100;
int n,x,y,s,ans,v[maxn+5];
vector<int> g[maxn+5];
void bfs(int q) {queue<int>w;w.push(q);v[q]=1;while(!w.empty()) {int e=w.front();w.pop();for(int i=0;i<g[e].size();i++) {int r=g[e][i];if(!v[r]) {v[r]=1;s++;w.push(r);}}}
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cin>>n>>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]) {v[i]=s=1;bfs(i);ans=max(ans,s);}}cout<<ans;return 0;
}