CF755C PolandBall and Forest 题解

Content

给定无向图的 \(n\) 个点的父亲节点，求无向图的联通块个数。

数据范围：\(1\leqslant n\leqslant 10^4\)。

Solution

并查集模板题。

我们将在当前节点和它的父亲节点连在一起，然后看不同的祖先节点的个数即可。

没学过并查集的同学建议先去做 P3367 【模板】并查集。

Code

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

#include <iostream>

using namespace std;

int n, a[10007], f[10007], vis[10007], ans;

int getfa(int x) {

	return (x == f[x]) ? x : f[x] = getfa(f[x]);

}

void unionn(int x, int y) {

	x = getfa(x), y = getfa(y);

	if(x != y) f[x] = y;

}

int main() {

	scanf("%d", &n);

	for(int i = 1; i <= n; ++i) f[i] = i;

	for(int i = 1; i <= n; ++i) {

		int x;

		scanf("%d", &x);

		unionn(x, i);

	}

	for(int i = 1; i <= n; ++i)

		if(!vis[getfa(i)]) ans++, vis[getfa(i)] = 1;

	printf("%d", ans);

	return 0;

}

巴特西

CF755C PolandBall and Forest 题解

Content

Solution

Code

最新文章

热门文章