AtCoder August 2022

ABC264 on 13rd

E. Blackout 2

Problem: https://atcoder.jp/contests/abc264/tasks/abc264_e

問題文

ある国には N 個の都市と M 個の発電所があります。これらを総称して地点と呼びます。
地点には 1,2,…,N+M の番号がつけられており、そのうち都市は地点 1,2,…,N で発電所は地点 N+1,N+2,…,N+M です。

この国には電線が E 本あり、電線 i ( 1≤i≤E ) は地点 Ui と地点 Vi を双方向に結びます。
また、ある都市に 電気が通っている とは、ある都市から電線をいくつか辿って少なくともひとつの発電所に辿り着くことができる状態を言います。

今、 Q 個のイベントが起こります。そのうち i ( 1≤i≤Q ) 番目のイベントでは電線 Xi が切れ、その電線を辿ることができなくなります。一度切れた電線は、その後のイベントにおいても切れたままです。

全てのイベントについて、そのイベントが終わった直後に電気が通っている都市の数を求めてください。

制約

• 入力は全て整数
• 1≤N,M
• N+M≤2×10^5
• 1≤Q≤E≤5×10^5
• 1≤Ui<Vi≤N+M
• i≠j ならば、 Ui≠Uj または Vi≠Vj
• 1≤Xi≤E
• Xi は相異なる

Solution:

At the first glance this may look like network flow, but it's actually union-find-set. Offline the queries and reverse the order, add the edges inside of cutting out the edges. A well disguised union-find-set.

Code: https://atcoder.jp/contests/abc264/submissions/34092352

// Problem Alias: abc264_e
// Url: https://atcoder.jp/contests/abc264/tasks/abc264_e

#include <cstdio>
#include <algorithm>
using namespace std;

// #define debugp(...) fprintf(stderr, __VA_ARGS__)
#define debugp(...) 

const int MAXN = 2e5+10;
const int MAXE = 5e5+10;
int N,M,E,Q;
int ans[MAXN];
int sz[MAXN];
int qs[MAXE];
struct {
  int u,v;
} e[MAXE];
bool cut[MAXE];
int res[MAXE];

int findans(int u)
{
  return ans[u] == u ? u : ans[u] = findans(ans[u]);
}
void merge(int u, int v)
{
  debugp("%d %d ", u, v);
  u = findans(u);
  v = findans(v);
  debugp("%d %d %d %d\n", u, v, sz[u], sz[v]);
  if (u == v)
    return;
  ans[v] = u;
  sz[u] += sz[v];
}

int main()
{
  int u,v;
  scanf("%d %d %d", &N, &M, &E);
  ans[0] = 0;
  sz[0] = 0;
  for (int j=1;j<=N;++j)
  {
    ans[j] = j;
    sz[j] = 1;
  }
  for (int j=N+1;j<=N+M;++j)
  {
    ans[j] = 0; // virtual energy source 0
  }
  for (int j=1;j<=E;++j)
  {
    scanf("%d %d", &u, &v);
    e[j] = {u,v};
  }
  fill(cut, cut+E+1, false);
  scanf("%d", &Q);
  for (int j=0;j<Q;++j)
  {
    scanf("%d", &qs[j]);
    cut[qs[j]] = true;
  }
  for (int j=1;j<=E;++j)
  {
    if (!cut[j])
    {
      merge(e[j].u,e[j].v);
    }
  }
  debugp("%d\n", sz[ans[0]]);
  for (int j=Q-1;j>=0;--j)
  {
    res[j] = sz[findans(0)]; // virtual energy source 0
    merge(e[qs[j]].u, e[qs[j]].v);
  }
  for (int j=0;j<Q;++j)
  {
    printf("%d\n", res[j]);
  }
  return 0;
}