目录
统计连通分量思路
统计连通分量的个数及其他属性（如：总点权，总边权等），思路有三种：DFS、BFS、并查集
DFS/BFS统计连通分量思路
DFS/BFS遍历图中所有顶点，DFS/BFS函数调用的次数即为连通分量个数，每次调用DFS/BFS函数会完全遍历一个连通分量的所有顶点（在遍历过程中可以统计其点权和）
并查集统计连通分量思路
1 录入边信息时，将边的两个顶点进行并查集操作合并到一个集合中 （一个集合表示一个连通子图），根节点为并查集中每个集合的唯一标识
2 录入完成后，遍历father[n]数组，将根节点相同的顶点统计到一个连通子图，并求所有连通子图的属性
统计连通分量总边权注意事项
计算每个连通分量的总边权时，如果不做处理，会重复计算每条边的边权，每个连通分量边权和统计结果为实际边权总和的两倍
如何解决边权重复计算的问题？
思路1
标记已经访问过的顶点，并且标记已经访问过的边，如此才能保证所有边都被遍历统计而且不被重复统计，最终统计的总边权和为实际总边权和
标记访问过的边，也有两种思路：1. 访问过边后将该边边权置为0（g[a][b]=g[b][a]=0）2. 访问过边后将其标记为已被访问（evis[a][b]=evis[b][a]=0）
思路2
DFS/BFS标记已经访问过的顶点，但顶点中要记录与该顶点直连的所有边的边权，最终统计的总边权和为实际总边权和的两倍（因为每条边的两个顶点都记录了该边的边权）
深度优先遍历（DFS）
DFS统计连通分量属性（邻接矩阵）
#include <iostream>
using namespace std;
const int maxn = 1000;
int n,k,wt[maxn],g[maxn][maxn],vis[maxn];//wt点权，g边权
void dfs(int i,int &head,int &num,int &tv) {
num++;
vis[i]=true;
if(wt[i]>wt[head])head=i;
for(int j=1; j<=n; j++) {
if(g[i][j]==0)continue;
tv+=g[i][j];
g[i][j]=g[j][i]=0; //访问后将边权置为0，防止重复统计
if(vis[j]==false)
dfs(j,head,num,tv);
}
}
void dfs_travel() {
int cct=0; //统计连通分量个数
for(int i=1; i<=n; i++) {
if(vis[i]==true)continue;
int head=i,num=0,tv=0; //head 记录最大点权顶点；num记录顶点数；tv记录总边权
dfs(i,head,num,tv);
cct++;
/*
在此处理各个连通分量
*/
}
}
int main(int argc,char * argv[]) {
int w,a,b;
scanf("%d %d",&n,&k);
for(int i=0; i<n; i++) {
scanf("%d %d %d",&a,&b,&w);// 录入边描述：顶点1，顶点2，权重
wt[a]+=w; //将边权记录到顶点
wt[b]+=w;
g[a][b]=w; //记录边权
g[b][a]=w;
}
dfs_travel(); //深度优先遍历
return 0;
}
DFS统计连通分量属性（邻接表）
#include <iostream>
#include <vector>
using namespace std;
const int maxn = 1000;
int n,k,wt[maxn],vis[maxn],evis[maxn][maxn];//wt点权，g边权
struct node {
int v;
int w; //边权
};
vector<node> g[maxn];
void dfs(int i,int &head,int &num,int &tv) {
num++;
vis[i]=1;
if(wt[i]>wt[head])head=i;
for(int j=0; j<=g[i].size(); j++) {
if(evis[i][j]==1)continue;
tv+=g[i][j].w;
evis[i][j]=evis[j][i]=1;
dfs(j,head,num,tv);
}
}
void dfs_travel() {
int cct=0; //统计连通分量个数
for(int i=1; i<=n; i++) {
if(vis[i]==1)continue;
int head=i,num=0,tv=0; //head 记录最大点权顶点；num记录顶点数；tv记录总边权
dfs(i,head,num,tv);
cct++;
/*
在此处理各个连通分量
*/
}
}
int main(int argc,char * argv[]) {
int n,w,a,b;
scanf("%d %d",&n,&k);
for(int i=0; i<n; i++) {
scanf("%d %d %d",&a,&b,&w);// 录入边描述：顶点1，顶点2，权重
wt[a]+=w; //将边权记录到顶点
wt[b]+=w;
g[a].push_back({b,w}); //记录边权
g[b].push_back({a,w});
}
dfs_travel(); //深度优先遍历
return 0;
}
广度优先遍历（BFS）
BFS统计连通分量属性（邻接矩阵）
#include <iostream>
#include <map>
#include <queue>
const int maxn=2010;
using namespace std;
map<string,int> si;
map<int,string> is;
map<string,int> ans;
int n,k,wt[maxn],g[maxn][maxn],vis[maxn],evis[maxn][maxn];//wt点权，g边权
void bfs(int now, int &head, int &num, int &tv) {
queue<int> q;
q.push(now);
vis[now]=true;
while(!q.empty()) {
int i = q.front();
q.pop();
num++;
if(wt[i]>wt[head])head=i;
for(int j=1; j<=n; j++) {
if(evis[i][j]==1||g[i][j]==0)continue;
tv+=g[i][j];
evis[i][j]=evis[j][i]=1; //边标记为已被访问
if(vis[j]==false) {
q.push(j);
vis[j]=true; //顶点标记为已被访问
}
}
}
}
void bfs_travel() {
int cct=0; //统计连通分量个数
for(int i=1; i<=n; i++) {
if(vis[i]==true)continue;
int head=i,num=0,tv=0; //head 记录最大点权顶点；num记录顶点数；tv记录总边权
bfs(i,head,num,tv);
cct++;
/*
在此处理各个连通分量
*/
}
}
int main(int argc,char * argv[]) {
int w,a,b;
scanf("%d %d",&n,&k);
for(int i=0; i<n; i++) {
scanf("%d %d %d",&a,&b,&w);// 录入边描述：顶点1，顶点2，权重
wt[a]+=w; //将边权记录到顶点
wt[b]+=w;
g[a][b]=w; //记录边权
g[b][a]=w;
}
bfs_travel(); //深度优先遍历
return 0;
}
BFS统计连通分量属性（邻接表）
#include <iostream>
#include <map>
#include <queue>
const int maxn=2010;
using namespace std;
map<string,int> si;
map<int,string> is;
map<string,int> ans;
int n,k,wt[maxn],vis[maxn],evis[maxn][maxn];//wt点权，g边权
struct node {
int v;
int w;
};
vector<node> g[maxn];
void bfs(int now, int &head, int &num, int &tv) {
queue<int> q;
q.push(now);
vis[now]=true;
while(!q.empty()) {
int i = q.front();
q.pop();
num++;
if(wt[i]>wt[head])head=i;
for(int j=0; j<g[i].size(); j++) {
node t = g[i][j];
if(evis[i][t.v]==1)continue;
tv+=g[i][t.v].w;
evis[i][t.v]=evis[t.v][i]=1; //边标记为已被访问
if(vis[t.v]==false) {
q.push(t.v);
vis[t.v]=true; //顶点标记为已被访问
}
}
}
}
void bfs_travel() {
int cct=0; //统计连通分量个数
for(int i=1; i<=n; i++) {
if(vis[i]==true)continue;
int head=i,num=0,tv=0; //head 记录最大点权顶点；num记录顶点数；tv记录总边权
bfs(i,head,num,tv);
cct++;
/*
在此处理各个连通分量
*/
}
}
int main(int argc,char * argv[]) {
int w,a,b;
scanf("%d %d",&n,&k);
for(int i=0; i<n; i++) {
scanf("%d %d %d",&a,&b,&w);// 录入边描述：顶点1，顶点2，权重
wt[a]+=w; //将边权记录到顶点
wt[b]+=w;
g[a].push_back({b,w}); //记录边权
g[b].push_back({a,w});
}
bfs_travel(); //深度优先遍历
return 0;
}
并查集（+路径压缩）
并查集计算连通分量属性（邻接矩阵）
#include <iostream>
using namespace std;
const int maxn=2010;
int n,k,father[maxn],wt[maxn],awt[maxn],anum[maxn],head[maxn];//wt点权，g边权
/* 并查集 初始化 */
void init() {
for(int i=1; i<=n; i++) father[i]=i;
}
/* 并查集 查+路径压缩 */
int find(int x) {
int a = x;
while(x!=father[x])
x=father[x];
while(a!=father[a]) {
int temp=a;
a=father[a];
father[temp]=x;
}
return x;
}
/* 并查集 并 */
int Union(int a, int b) {
int x = find(a);
int y = find(b);
if(x<=y)father[y]=x;
else father[x]=y;
}
int main(int argc,char * argv[]) {
init();
int w,a,b;
scanf("%d %d",&n,&k);
for(int i=0; i<n; i++) {
scanf("%d %d %d",&a,&b,&w);// 录入边描述：顶点1，顶点2，权重
Union(a,b);
wt[a]+=w; //将边权记录到顶点
wt[b]+=w;
}
for(int i=1; i<=n; i++) {
int r = find(i);
anum[r]++; //连通分量 总人数增加1
awt[r]+=wt[i]; //连通分量总边权 将边权记录到边的两个顶点中，计算总权重增加 因为有重复计算，为实际边权两倍
if(wt[head[r]]<wt[i]) {
head[r]=i;
}
}
return 0;
}
并查集计算连通分量属性（邻接表）
#include <iostream>
#include <vector>
using namespace std;
const int maxn=2010;
int n,k,father[maxn],wt[maxn];//wt点权，g边权
struct node { //定义每个连通块的属性
int anum,awt,head; //总人数，总权重,队首整数编号
} cc[maxn]; //连通分量数组
/* 并查集 初始化 */
void init() {
for(int i=0; i<maxn; i++) father[i]=i;
}
/* 并查集 查 */
int find(int x) {
int a = x;
while(x!=father[x])
x=father[x];
while(a!=father[a]) {
int temp=a;
a=father[a];
father[temp]=x;
}
return x;
}
/* 并查集 并 */
void Union(int a, int b) {
int x = find(a);
int y = find(b);
if(x<=y)father[y]=x;
else father[x]=y;
}
int main(int argc,char * argv[]) {
init();
int w,a,b;
scanf("%d %d",&n,&k);
for(int i=0; i<n; i++) {
scanf("%d %d %d",&a,&b,&w);// 录入边描述：顶点1，顶点2，权重
Union(a,b);
wt[a]+=w; //将边权记录到顶点
wt[b]+=w;
}
for(int i=1; i<=n; i++) {
int r = find(i);
cc[r].anum++; //连通分量 总人数增加1
cc[r].awt += wt[i]; //连通分量总边权 将边权记录到边的两个顶点中，计算总权重增加 因为有重复计算，为实际边权两倍
if(wt[cc[r].head]<wt[i]) {
cc[r].head=i;
}
}
return 0;
}