并查集

#include <iostream>
#include <stack>
#include <cmath>
#include <vector>
#include <string.h>
#include <queue>
#include <stdio.h>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#define int long long
#define double long double
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int n, m, wi;
int w[N], v[N], fa[N], dp[N];
int find(int x)
{
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void init()
{
	for(int i = 1; i <= n; i++)
	{
		fa[i] = i;
	}
}
signed main()
{
	cin >> n >> m >> wi;
	init();
	for(int i = 1; i <= n; i++)
	{
		cin >> w[i] >> v[i];
	}
	int x, y;
	while(m--)
	{
		cin >> x >> y;
		int xx = find(x);
		int yy = find(y);
		fa[xx] = yy;
	}
	for(int i = 1; i <= n; i++)
	{
		if(fa[i] != i)
		{
			int ii = find(i);
			v[ii] += v[i];
			v[i] = 0;
			w[ii] += w[i];
			w[i] = 0;
		}
	}
	for(int i = 1; i <= n; i++)
	{
		for(int j = wi; j >= w[i]; j--)
		{
			dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
		}
	}
	cout << dp[wi] << endl;
	return 0;
}