题目链接：ZOJ4109-Welcome Party

题意：

n个人，m对朋友关系，当一个人进入大厅时，大厅内没有他的朋友他就会不高兴，问最少的不高兴人数，和最小字典序的进入顺序。

题解：

最少不高兴人数即是连通快的个数。然后最小字典序即用优先队列维护宽搜即可。注意几个比较坑的地方：

1. 不能用memset，T到爆炸。
2. 搜连通块时不能用dfs，会爆栈。
3. 不能使用STL自带的优先队列，会爆内存，需要手写堆。

参考代码：

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const int MAXN = 1000006;
int T, n, m;
int edge_v[MAXN * 2], edge_nxt[MAXN*2];
int ecnt = 0, fir[MAXN];
void addedge(int u, int v)
{
    edge_v[ecnt] = v;
    edge_nxt[ecnt] = fir[u];
    fir[u] = ecnt++;
}
int tot;
bool used[MAXN], col[MAXN];
void dfs(int u)
{
    col[u] = 1;
    for (int i = fir[u]; i != -1; i = edge_nxt[i])
    {
        int v = edge_v[i];
        if (col[v])
            continue;
        dfs(v);
    }
}
int Heap[MAXN], sum;
void node_swap(int x, int y)
{
    int temp = Heap[x];
    Heap[x] = Heap[y];
    Heap[y] = temp;
}
void siftdown(int i) //i表示操作的结点编号（从1开始）
{
    while (2 * i <= sum) 
    {
        int minn = Heap[2 * i], temp = 2 * i;
        if (2 * i + 1 <= sum && Heap[2 * i] > Heap[2 * i + 1])
        {
            minn = Heap[2 * i + 1];
            temp = 2 * i + 1;
        }
        if (Heap[i] > minn)
        {
            node_swap(i, temp);
            i = temp;
        }
        else
            break;
    }
}
void siftup(int i)
{ //i表示操作的结点编号（从1开始）
    while (i != 1)
    {
        if (Heap[i] < Heap[i / 2])
        {
            node_swap(i, i / 2);
            i /= 2;
        }
        else
            break;
    }
}
int delete_min()
{
    int t = Heap[1];
    Heap[1] = Heap[sum];
    sum--;
    siftdown(1);
    return t;
}
void PUSH(int u)
{
    sum++;
    Heap[sum] = u;
    siftup(sum);
}
int main()
{
    //freopen("in.dat", "r", stdin);
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &n, &m);
        ecnt = tot = sum = 0;
        for (int i = 1; i <= n; i++)
            fir[i] = -1, col[i] = used[i] = 0;
        for (int i = 1; i <= m; i++)
        {
            int u, v;
            scanf("%d%d", &u, &v);
            addedge(u, v), addedge(v, u);
        }
        for (int i = 1; i <= n; i++)
        {
            if (!col[i])
            {
                tot++;
                PUSH(i);
                used[i] = 1;
                dfs(i);
            }
        }
        printf("%d\n", tot);
        bool flag = 1;
        while (sum != 0)
        {
            int u = delete_min();
            if (flag)
                printf("%d", u), flag = 0;
            else
                printf(" %d", u);
            for (int i = fir[u]; i != -1; i = edge_nxt[i])
            {
                int v = edge_v[i];
                if (used[v])
                    continue;
                used[v] = 1;
                PUSH(v);
            }
        }
        puts("");
    }
    return 0;
}