题意:
n个人,m对朋友关系,当一个人进入大厅时,大厅内没有他的朋友他就会不高兴,问最少的不高兴人数,和最小字典序的进入顺序。
题解:
最少不高兴人数即是连通快的个数。然后最小字典序即用优先队列维护宽搜即可。注意几个比较坑的地方:
- 不能用memset,T到爆炸。
- 搜连通块时不能用dfs,会爆栈。
- 不能使用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;
}