AcWing 395. 分离的路径

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

using namespace std;
typedef long long ll;
struct node {int next, to;}e[A];
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[A], b[A];
int dfn[A], cnt, low[A], vis[A], kn, sta[A], top, bl[A], ans, in[A];
void tarjan(int fr, int fa) {
  dfn[fr] = low[fr] = ++cnt, sta[++top] = fr, vis[fr] = 1;
  for (int i = head[fr]; i; i = e[i].next) {
    int ca = e[i].to;
    if (ca == fa) continue;
    if (!dfn[ca]) tarjan(ca, fr), low[fr] = min(low[fr], low[ca]);
    else if (vis[ca]) low[fr] = min(low[fr], dfn[ca]);
  }
  if (low[fr] == dfn[fr]) {
    int p; kn++;
    do {
      p = sta[top--];
      vis[p] = 0;
      bl[p] = kn;
    } while (p != fr);
  }
}
map<int, int> ap[A];

int main(int argc, char const *argv[]) {
  cin >> n >> m;
  for (int i = 1; i <= m; i++) scanf("%d%d", &a[i], &b[i]), add(a[i], b[i]), add(b[i], a[i]);
  for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i, i);
  for (int i = 1; i <= m; i++) if (bl[a[i]] != bl[b[i]] and !ap[bl[a[i]]][bl[b[i]]])
    ap[bl[a[i]]][bl[b[i]]] = ap[bl[b[i]]][bl[a[i]]] = 1, in[bl[a[i]]]++, in[bl[b[i]]]++;
  for (int i = 1; i <= kn; i++) if (in[i] == 1) ans++;
  cout << (ans + 1) / 2 << endl;
}