POJ3177 Redundant Paths【tarjan边双联通分量】

题目大意

给你一个有重边的无向图图，问你最少连接多少条边可以使得整个图双联通

思路

就是个边双的模板

注意判重边的时候只对父亲节点需要考虑

你就dfs的时候记录一下出现了多少条连向父亲的边就可以了

然后和有向图不一样的是，在这里非树边的更新不用判断点是不是在栈内，因为无向图中没有u可以到达v但是v不能到达u的情况

//Author: dream_maker

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<stack>

using namespace std;

//----------------------------------------------

//typename

typedef long long ll;

//convenient for

#define fu(a, b, c) for (int a = b; a <= c; ++a)

#define fd(a, b, c) for (int a = b; a >= c; --a)

#define fv(a, b) for (int a = 0; a < (signed)b.size(); ++a)

//inf of different typename

const int INF_of_int = 1e9;

const ll INF_of_ll = 1e18;

//fast read and write

template <typename T>

void Read(T &x) {

  bool w = 1;x = 0;

  char c = getchar();

  while (!isdigit(c) && c != '-') c = getchar();

  if (c == '-') w = 0, c = getchar();

  while (isdigit(c)) {

    x = (x<<1) + (x<<3) + c -'0';

    c = getchar();

  }

  if (!w) x = -x;

}

template <typename T>

void Write(T x) {

  if (x < 0) {

    putchar('-');

    x = -x;

  }

  if (x > 9) Write(x / 10);

  putchar(x % 10 + '0');

}

//----------------------------------------------

const int N = 5e3 + 10;

const int M = 1e4 + 10;

struct Edge {

  int u, v, nxt;

} E[M << 1];

int head[N], tot = 0;

int n, m, du[N];

void add(int u, int v) {

  ++tot;

  E[tot].u = u;

  E[tot].v = v;

  E[tot].nxt = head[u];

  head[u] = tot;

}

int dfn[N], low[N], bel[N], ind = 0, cnt_bcc = 0;

stack<int> st;

void tarjan(int u, int fa) {

  dfn[u] = low[u] = ++ind;

  st.push(u);

  bool k = 0;

  for (int i = head[u]; i; i = E[i].nxt) {

    int v = E[i].v;

    if (fa == v && !k) {

      k = 1;

      continue;

    }

    if (!dfn[v]) {

      tarjan(v, u);

      low[u] = min(low[u], low[v]);

    } else {

      low[u] = min(low[u], dfn[v]);

    }

  }

  if (low[u] == dfn[u]) {

    int now;

    ++cnt_bcc;

    do {

      now = st.top(); st.pop();

      bel[now] = cnt_bcc;

    } while (now != u);

  }

}

int main() {

  Read(n), Read(m);

  fu(i, 1, m) {

    int u, v;

    Read(u), Read(v);

    add(u, v);

    add(v, u);

  }

  fu(i, 1, n) if (!dfn[i]) tarjan(i, 0);

  for (int i = 1; i <= tot; i += 2) {

    int u = E[i].u, v = E[i].v;

    if (bel[u] != bel[v]) {

      du[bel[u]]++;

      du[bel[v]]++;

    }

  }

  int ans = 0;

  fu(i, 1, cnt_bcc)

    if (du[i] == 1) ans++;

  ans = (ans + 1) >> 1;

  Write(ans);

  return 0;

}

巴特西

POJ3177 Redundant Paths【tarjan边双联通分量】

题目大意

思路

最新文章

热门文章