AcWing 365. 圓桌騎士

#include <bits/stdc++.h>
#define
#define

using namespace std;
typedef long long ll;
struct node {int next, to;}e[B];
int head[A], num;
void add(int fr, int to) {e[++num].next = head[fr]; e[num].to = to; head[fr] = num;}
int n, m, a, b; bool hate[A][A], exi[A], bl[A];
int dfn[A], cnt, low[A], col[A], sta[A], top;
vector<int> v;
bool check(int s) {
  queue<int> q; q.push(s); col[s] = 1;
  while (!q.empty()) {
    int fr = q.front(); q.pop(); int color = (col[fr] == 1 ? 2 : 1);
    for (int i = head[fr]; i; i = e[i].next) {
      int ca = e[i].to;
      if (!exi[ca]) continue;
      if (!col[ca]) col[ca] = color, q.push(ca);
      else if (col[ca] != color) return true;
    }
  }
  return false;
}
void tarjan(int fr) {
  dfn[fr] = low[fr] = ++cnt; sta[++top] = fr;
  for (int i = head[fr]; i; i = e[i].next) {
    int ca = e[i].to;
    if (!dfn[ca]) {
      tarjan(ca); low[fr] = min(low[fr], low[ca]);
      if (dfn[fr] <= low[ca]) {
        v.clear(); int p;
        do {
          p = sta[top--];
          v.push_back(p);
        } while (p != ca);
        v.push_back(fr);
        memset(col, 0, sizeof col); memset(exi, 0, sizeof exi);
        for (auto j : v) exi[j] = 1;
        if (check(v[0])) for (auto j : v) bl[j] = 1;
      }
    }
    else low[fr] = min(low[fr], dfn[ca]);
  }
}

int main(int argc, char const *argv[]) {
  while (scanf("%d%d", &n, &m) and n and m) {
    memset(head, 0, sizeof head); num = 0; cnt = 0; memset(bl, 0, sizeof bl);
    memset(dfn, 0, sizeof dfn); memset(low, 0, sizeof low); top = 0;
    memset(sta, 0, sizeof sta); memset(hate, 0, sizeof hate);
    for (int i = 1; i <= m; i++) scanf("%d%d", &a, &b), hate[a][b] = hate[b][a] = 1;
    for (int i = 1; i <= n; i++)
      for (int j = i + 1; j <= n; j++)
        if (!hate[i][j]) add(i, j), add(j, i);
    for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i);
    int ans = n;
    for (int i = 1; i <= n; i++) if (bl[i]) ans--;
    printf("%d\n", ans);
  }
  return 0;
}