P3535. TOU-Tour de Byteotia

发表于 2023-11-14 分类于洛谷阅读次数： Waline：本文字数： 300 阅读时长 ≈ 1 分钟

考点

并查集

题解

#include <bits/stdc++.h>
using namespace std;
const int LEN = 1e6 + 50;
int n, m, k, fa[LEN];
vector<int> e[LEN];

int find(int x) {
  if (fa[x] == x) return x;
  return fa[x] = find(fa[x]);
}

void join(int x, int y) {
  int a = find(x), b = find(y);
  fa[a] = b;
}

int main() {
  int x, y, ans = 0;
  cin >> n >> m >> k;
  for (int i = 1; i <= m; ++i) {
    cin >> x >> y;
    e[x].emplace_back(y), e[y].emplace_back(x);
  }
  for (int u, v, i = n; i > k; --i) {
    fa[i] = u = i;
    for (int j = 0; j < e[u].size(); ++j) {
      v = e[u][j];
      if (fa[v] && find(u) != find(v)) join(u, v);
    }
  }
  for (int u, v, i = k; i >= 1; --i) {
    fa[i] = u = i;
    for (int j = 0; j < e[u].size(); ++j) {
      v = e[u][j];
      if (!fa[v]) continue;
      if (find(u) == find(v))
        ++ans;
      else
        join(u, v);
    }
  }
  cout << ans;
  return 0;
}