- 题意:这道题就是给出一张无向图,然后每次消除一个点,一共消除k次,问每次该图连通块数量(一个点也算一个连通块)
- 思路:逆向思维 + 并查集。
- 解析:每次破坏后求连通块无思路,若从最后破坏完毕后,往回模拟,实际上就是进行k次修复,那么一开始我们假设每个点都是一个连通块,进行k次破坏后,通过对现存的点进行判断存在有几个连通块,接着k次修复,每一次修复一个点,再对该点与其相邻未被破坏的点进行判断,判断两点是否在不在一个连通块中,若是则连通块总数量减一。
- 代码:
#include<iostream>
#include<vector>
using namespace std;
const int N = 4e5 + 5;
vector<int> g[N];
int brk[N], res[N], par[N], bp[N];
int n, m, k;
int find(int x)
{
return par[x] == x ? x : par[x] = find(par[x]);
}
void merge(int x, int y)
{
par[find(x)] = find(y);
}
int main()
{
cin >> n >> m;
for(int i = 0; i < n; i++) par[i] = i;
for(int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
cin >> k;
for(int i = 0; i < k; i++)
{
int x;
cin >> x;
brk[x] = 1; //标记被炸的星球
bp[i] = x; //记录第几号星球被破坏
}
int cnt = n; //当前连通块个数(假设每个星球都为一个连通块)
for(int i = 0; i < n; i++)
{
if(brk[i]) //若该星球被破坏则连通块数量减一
{
cnt --;
continue;
}
for(int j = 0; j < g[i].size(); j++)
{
int v = g[i][j];
if(!brk[v] && find(v) != find(i)) //若星球v没被破坏且与星球i不在一个连通块则将两者进行合并,连通块数量也随之减一
{
merge(i, v);
cnt --;
}
}
}
res[k] = cnt;
for(int i = k - 1; i >= 0; i--)
{
int v = bp[i];
brk[v] = 0; //星球v已经修复
cnt ++; //星球v修复后连通块数量+1
for(int j = 0; j < g[v].size(); j++)
{
int u = g[v][j];
if(!brk[u] && find(u) != find(v))
{
merge(u, v);
cnt --;
}
}
res[i] = cnt;
}
for(int i = 0; i <= k; i++)
cout << res[i] << endl;
return 0;
}