#include<bits/stdc++.h>
#define maxn 20002
using namespace std;
int n,m,k;
int dp,siz[maxn],dp1;
struct node{
    int fa[maxn];
    void init(){
        for(int i=1;i<=n;i++){
            fa[i]=i;
            siz[i]=1;
        }
    }
    int getfather(int x){
       return fa[x]==x?x:fa[x]=getfather(fa[x]); 
    }
    void hb(int x,int y){
        int fax=getfather(x);
        int fay=getfather(y);
        if(fax!=fay){
            if(siz[fax]>siz[fay]){
                swap(fax,fay);
            }
            fa[fax]=fay;
            siz[fay]+=siz[fax];
        }
    }
}bcj;
int main(){
    scanf("%d%d%d",&n,&m,&k);
    bcj.init();
    for(int i=1;i<=k;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        bcj.hb(x,y);
    }
    for(int i=1;i<=n;i++){
        if(bcj.getfather(i)==i){
            if(abs(m-dp)>abs(m-dp-siz[i]))
            dp+=siz[i];
            //cout<<abs(m-dp[cnt-1])<<" "<<abs(m-dp[cnt-1]-siz[i])<<endl;
        }
    }
	for(int i=n;i>=0;i--){
        if(bcj.getfather(i)==i){
            if(abs(m-dp1)>abs(m-dp1-siz[i]))
            dp1=dp1+siz[i];
            //cout<<abs(m-dp[cnt-1])<<" "<<abs(m-dp[cnt-1]-siz[i])<<endl;
        }
    }
    if(abs(m-dp1)==abs(m-dp)){
		printf("%d",min(dp,dp1));
	}else if(abs(m-dp1)>abs(m-dp)){
		printf("%d",dp);
	}else printf("%d",dp1);
    return 0;
}

本题正解是dp，但是可以通过正向贪心选一遍，反向贪心选一遍来通过。

求是数据水了还是可以这样做。