畅通工程2，对于并查集理解_P1319

努力努力在努力

TA的个人主页 >

文章

粉丝

176

获赞

访问

12.0k

畅通工程2，对于并查集理解

努力努力在努力

发布于2023年2月24日 20:10

阅读数 3.1k

#include <algorithm>

#include <bits/stdc++.h>

#include <cmath>

#include <cstdio>

#include <cstdlib>

#include <math.h>

#include <queue>

#include <string>

using namespace std;

int fa[1002];

int find(int x){

if(fa[x]==x) return x;

fa[x] = find(fa[x]);

return fa[x];

}

int main() {

int n,m,x,y,total;

while (cin>>n>>m) {

if(n==0) return 0;

total = 0;

for(int i=0;i<1002;++i)

fa[i] = i;

for(int i=0;i<m;++i){

cin>>x>>y;

if(find(x)!=find(y)){

//既然题目所给这两个道路是连通的，也就证明这两个道路中有一条边故需要++total 而N个顶点连通至少需要n-1条边所以最少还需修建多少道路就出来了

fa[find(x)] = find(y);

&nbs...