洛谷P1197.星球大战

• 并查集 + 贪心

• 正着不好想，逆向思维将摧毁变为修建

  • 一开始处理图的时候就是将所有没有被炸的点能连的连在一起(图论)
  • 并求出连通块数量(并查集)
  • 然后逐步反向将被摧毁的点复原

•   #include <bits/stdc++.h>
    using namespace std;
    
    const int N = 400010;
    int res;
    int n,m,k;
    int p[N];
    int h[N],e[N],ne[N],s[N],idx;
    bool st[N];
    
    void add(int a,int b)
    {
        e[idx] = b,s[idx] = a,ne[idx] = h[a],h[a] = idx++;
    }
    
    int find(int x)
    {
        if(p[x] != x) return p[x] = find(p[x]);
        return x;
    }
    
    int main()
    {
        //连无向边
        memset(h,-1,sizeof h);
        memset(st,true,sizeof st);
        cin>>n>>m;
        iota(p,p+n+1,0);
        //连无向边
        for(int i=1;i<=m;i++)
        {
            int x,y;
            cin>>x>>y;
            add(x,y),add(y,x);
        }
        cin>>k;
        //pk存被摧毁的星球，ans存答案
        stack<int> pk,ans;
        for(int i=1;i<=k;i++)
        {
            int q;
            cin>>q;
            //标记这个星球被摧毁
            st[q] = false,pk.push(q);
        }
        //无向边 m变成2倍
        // res 为 所有星球独立一共n-k个
        m = 2*m,res = n-k;
        for(int i=1;i<=m;i++)
        {
            //对于每一条边的起点和终点
            int S = find(s[i]),E = find(e[i]);
            //如果都没有被摧毁，并且没有在并查集里连上
            if(st[e[i]] && st[s[i]] && S != E)
            {
                res --;
                p[E] = S;
            }
        }
        ans.push(res);
        while(pk.size())
        {
            //取当前tot为修复的星球
            int tot = pk.top();
            pk.pop();
    
            res ++;
            st[tot] = true;
            //tot作为起点的所有边
            for(int i=h[tot];i!=-1;i=ne[i])
            {
                int j = e[i];
                int S = find(tot) ,E = find(e[i]);
                //另一个星球没有被摧毁 连通块--
                if(st[j] && S != E)
                {
                    res --;
                    p[E] = S;
                }
            }
            ans.push(res);
        }
        //逆序输出答案(用栈)
        while(ans.size())
        {
            res = ans.top();
            ans.pop();
            cout<<res<<endl;
        }
        return 0;
    }