题目如下

在无向图中，如果从顶点v i 到顶点v j 有路径，则称v i 和v j 连通，如果图中任意两个顶点之间都连通，则称该图为连通图，否则，称该图为非连通图，则其中的极大连通子图称为连通分量，这里所谓的极大是指图中包含的顶点个数极大。例如，一个无向图有5个顶点，1-3-5是连通的，2是连通的，4是连通的，则这个无向图有3个连通分量。

输入第一行，一个整数TT，表示一共有TT组测试样例(1≤T≤50)(1≤T≤50)。

对于每组测试样例，第一行包含两个整数NN和MM，分别表示图有NN个顶点，MM条边。接下来MM行，每行有两个整数uu和vv，表示顶点uu和vv相连。（1≤N≤20，1≤M≤2001≤N≤20，1≤M≤200）

输出对于每组数据，输出一行，一个整数，表示连通分量的个数

输入样例 1 2 3 1 1 2 3 2 3 2 1 2 输出样例1 2 1

代码如下

CPP

#include<bits/stdc++.h>
using namespace std;
int t,n,m,a[50][50],vis[210],u,v;
void dfs(int x) {
	vis[x]=1;
	for(int i=1; i<=n; i++) {
		if(a[x][i]&&vis[i]==0) {
			dfs(i);
		}
	}
	return;
}
int main() {
	cin>>t;
	for(int o=0; o<t; o++) {
		memset((int*)a,0,sizeof(int)*50*50);
		memset(vis,0,sizeof(vis));
		int cnt=0;
		cin>>n>>m;
		for(int i=1; i<=m; i++) {
			cin>>u>>v;
			a[u][v]=1;
			a[v][u]=1;
		}
		for(int i=1; i<=m; i++) {
			dfs(i);
			cnt++;
		}
		cout<<cnt<<endl;
	}
	return 0;
}

大佬，帮帮我~（20分）

讨论操作

题目如下

代码如下

回复

相关推荐

大佬，帮帮我~（20分）