当前位置：首页 > article >正文

洛谷P1197.星球大战

article 2024/11/17 0:44:56

洛谷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;
  }