自用并查集思路

2026-09-15 17:16:42

发布于：广东

2阅读

0回复

0点赞

#include<bits/stdc++.h>
using namespace std;

int n,fa[105];


int find(int x){
    if(fa[x] != x)		//每次查找父节点是否等于它自己 是就代表这是个根节点 
        fa[x] = find(fa[x]);//不是根节点 更新 递归 
        
    return fa[x];//返回最后找到的根值 
}

void unite(int x, int y){//此段合并节点 
    int fx = find(x);
    int fy = find(y);
    if(fx != fy){
        fa[fx] = fy;//x的根节点指向y的根节点 此时x根节点不再是fa[x] 而是fy 
    }
}

int main(){
	cin >> n;
	for(int i=1;i<=n;i++){
		fa[i]=i;
		unite(i-1,i);
	}
	for(int i=1;i<=n;i++){
		cout << find(i) << " ";
	}
		
}