[JSOI2008]星球大战

题目链接:星球大战

  • 题意:这道题就是给出一张无向图,然后每次消除一个点,一共消除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;
}

上一篇:linux内存碎片


下一篇:linux 系统调用