WA 4个 T一个
size中有0会影响结果吗?
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
const int N = 2e4 + 10;
int fa[N],size[N];
int dp[N];
inline void init(){
for(int i = 1;i <= N - 20;i++){
fa[i] = i;
size[i] = 1;
}
}
int get(int x){
if(x == fa[x]) return x;
else return fa[x] = get(fa[x]);
}
void modify(int x,int y){
x = get(x);y = get(y);
fa[x] = y;
size[y] += size[x];
size[x] = 0;
}
int main(){
cin >>n >> m>> k;
init();
for(int i = 1;i <= k;i++){
int a,b;
cin >>a >>b;
modify(a,b);
}
for(int i = 1;i <= n;i++){
for(int j = m;j >= size[i];j--){
if(j >= size[i]) dp[j] = max(dp[j - size[i]] + size[i],dp[j]);
}
}
cout<< dp[m];
return 0;
}