先通过并查集处理出来有多少种不同的集合，每一个集合有多少人。一定要不要忘记了与别的没有联系的独立点。

并查集的时候能够通过hash处理出来每一个数目同样的集合的个数。

这样以人数为权值。个数为限制进行多重背包，结果就是答案。

题目链接：http://codevs.cn/problem/3372/

#include <algorithm>

#include <iostream>

#include <stdlib.h>

#include <string.h>

#include <iomanip>

#include <stdio.h>

#include <string>

#include <queue>

#include <cmath>

#include <stack>

#include <map>

#include <set>

#define eps 1e-8

#define M 1000100

#define LL long long

//#define LL long long

#define INF 0x3f3f3f

#define PI 3.1415926535898

#define mod 1000000007

const int maxn = 30010;

using namespace std;

int vis1[maxn];

int vis2[maxn];

int vis[maxn];

int num[maxn];

int dp[2*maxn];

int fa[maxn];

struct node

{

    int snum;

    int sum;

} p[maxn];

int n;

void init()

{

    for(int i = 0; i <= n; i++) fa[i] = i;

    memset(vis1, 0, sizeof(vis1));

    memset(vis2, 0, sizeof(vis2));

    memset(dp, 0, sizeof(dp));

    memset(vis, 0, sizeof(vis));

}

int Find(int x)

{

    if(x != fa[x]) fa[x] = Find(fa[x]);

    return fa[x];

}

void add(int x, int y)

{

    int x1, y1;

    x1 = Find(x);

    y1 = Find(y);

    if(x1 != y1) fa[x1] = y1;

}

int main()

{

    int m, k;

    while(~scanf("%d %d %d",&n, &m, &k))

    {

        init();

        int x, y;

        for(int i = 0; i < k; i++)

        {

            scanf("%d %d",&x, &y);

            vis[x] = 1;

            vis[y] = 1;

            add(x, y);

        }

        int ans = 0;

        int xsum = 0;

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

        {

            if(!vis[i])

            {

                xsum ++;

                continue;

            }

            int s = Find(i);

            vis1[s] ++;

        }

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

        {

            if(!vis1[i]) continue;

            num[ans++] = vis1[i];

        }

        sort(num, num+ans);

        for(int i = 0; i < ans; i++) vis2[num[i]]++;

        int cnt = 0;

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

        {

            if(!vis2[i]) continue;

            p[cnt].snum = i;

            p[cnt++].sum = vis2[i];

        }

        int v = 2*(m+1);

        dp[0] = 1;

        for(int i = 0; i < cnt; i++)

        {

            for(int j = v; j >= 0; j--)

            {

                if(!dp[j]) continue;

                for(int kk = 1; kk <= p[i].sum; kk++)

                {

                    if(kk*p[i].snum+j > v) break;

                    if(dp[kk*p[i].snum+j]) break;

                    dp[kk*p[i].snum+j] = 1;

                }

            }

        }

        int lx, rx;

        for(int i = m; i >= 0; i--)

        {

            if(dp[i])

            {

                lx = i;

                break;

            }

        }

        for(int i = m; i <= 2*(m+1); i++)

        {

            if(dp[i])

            {

                rx = i;

                break;

            }

        }

        lx = max(lx, 0);

        rx = min(rx, 2*(m+1));

        int sx = abs(m-lx);

        int sy = abs(rx-m);

        if(sx <= xsum)

        {

            sx = 0;

            lx = m;

        }

        else

        {

            sx -= xsum;

            lx += xsum;

        }

        if(sy < sx)

        {

            cout<<rx<<endl;

            continue;

        }

        cout<<lx<<endl;

    }

    return 0;

}

/*

10 4 9

8 2

1 5

5 10

9 7

10 3

3 4

4 6

8 9

6 8

0

5 3 3

1 2

2 3

3 4

4

*/