文章

4

粉丝

176

获赞

8

访问

11.7k

头像
畅通工程2,对于并查集理解
P1319 浙江大学机试题
发布于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...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发