倒计时41天

倒计时61天-CSDN博客

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 6;
const int inf = 0x3f3f3f3f;
int a[N];

int find(int x) {
	if (x != a[x]) {
		a[x] = find(a[x]);
	}
	return a[x];
}

void solve() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	int x;
	cin >> x;
	cout << find(x);
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	int t = 1;
	//cin>>t;
	while (t--) {
		solve();
	}
	return 0;
}

//***********************************************************************************//

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 6;
const int inf = 0x3f3f3f3f;
int a[N];

int find(int x) {
	if (x != a[x]) {
		a[x] = find(a[x]);
	}
	return a[x];
}

void find2(int x, int y) {
	int fx = find(x);
	int fy = find(y);
	if (fx != fy) {
		a[fx] = fy;
	}
}

void solve() {
	int n, m;
	cin >> n >> m;

	for (int i = 1; i <= n; i++)
		a[i] = i;
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		find2(x, y);
	}
	int cn = -1;
	for (int i = 1; i <= n; i++) {
		if (i == a[i])
			cn++;
	}
	cout << cn << endl;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	int t = 1;
	//cin>>t;

	while (t--) {
		solve();
	}
	return 0;
}

//***********************************************************************************//

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 6;
const int inf = 0x3f3f3f3f;
int a[N];

struct node {
	int x, y, si;
} no[N];

bool cmp(node xx, node yy) {
	return xx.si < yy.si;
}

int find(int x) {
	if (x != a[x]) {
		a[x] = find(a[x]);
	}
	return a[x];
}

void find2(int x, int y) {
	int fx = find(x);
	int fy = find(y);
	if (fx != fy) {
		a[fx] = fy;
	}
}

void solve() {
	int n, m, ans = 0;
	cin >> n >> m;

	for (int i = 1; i <= n; i++)
		a[i] = i;
	for (int i = 0; i < m; i++) {
		int x, y, si;
		cin >> x >> y >> si;
		no[i] = {x, y, si};
	}
	sort(no, no + m, cmp);
	for (int i = 0; i < m; i++) {
		if (find(no[i].x) != find(no[i].y)) {
			ans += no[i].si;
			find2(no[i].x, no[i].y);
		}
	}
	cout << ans;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	int t = 1;
	//cin>>t;

	while (t--) {
		solve();
	}
	return 0;
}