题目
在图论里，伪森林是指一个无向图，其中每个连通块最多只有一个环。图 \(G\) 的极大伪森林是指那些不能被包含进更大伪森林的伪森林子图。伪森林的“大”与“小”是通过边权值总和来比较的，边权值总和越大，伪森林就越“大”。
输入
输入包含多个测试用例。每个测试用例的第一行有两个整数 \(n\) (\(0 < n \le 10000\))、\(m\)(\(0 \le m \le 100000\))，分别表示顶点数和边数。接下来 \(m\) 行，每行三个整数 \(u\)、\(v\)、\(c\)，表示顶点 \(u\) 和顶点 \(v\) 之间有一条权值为 \(c\) (\(0 < c \le 10000\)) 的边。保证没有自环和重边。
当遇到一行“\(0\) \(0\)”时，表示输入结束。
输出
输出最大伪森林中所有边权值的总和。
思路
伪森林的定义为：
伪森林是指一个无向图，其中每个连通块最多只有一个环。
那么我们采取 \(Kruskal\) 算法，并采取带权并查集，记录每个代表的权值就是它所在的连通块中环的个数。只要本次合并不会产生包含两个环以上的连通块，那么合并合法。
代码时间复杂度就相当于 \(Kruskal\) 算法的时间复杂度，不会超时。
代码
#include <bits/stdc++.h>
#define N 10010
#define M 100010
using namespace std;
struct edge {int x,y;int val;
};
bool operator<(const edge &a,const edge &b) {return a.val>b.val;
}
int n,m,ans,u,v,w;
edge ed[M];
int fa[N],val[N];
int find(int u) {if(fa[u]==u) return u;else return fa[u]=find(fa[u]);
}
int main() {ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);while(true){cin>>n>>m;if(n==0 && m==0) break;for(int i=1;i<=m;i++) {cin>>ed[i].x>>ed[i].y>>ed[i].val;ed[i].x++; ed[i].y++;}sort(ed+1,ed+1+m);for(int i=1;i<=n;i++) {fa[i]=i;val[i]=0;}ans=0;for(int i=1;i<=m;i++) {u=ed[i].x; v=ed[i].y;w=ed[i].val;if(find(u)==find(v)) {if(val[find(u)]==0) {val[find(u)]++;ans+=w;}}else {if(val[find(u)]+val[find(v)]<=1) {val[find(v)]+=val[find(u)];fa[find(u)]=find(v);ans+=w;}}}cout<<ans<<'\n';}return 0;
}