GRAPH_ - Tìm khớp và cầu (Cơ bản)
Tác giả: RR
Ngôn ngữ: C++
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <cstdlib>
#include <set>
#include <queue>
#include <stack>
#include <memory.h>
#include <cassert>
#include <sstream>
#define oo 1000111000
#define PI acos(-1.0)
#define FOR(i,a,b) for(int i = (a), _b = (b); i <= _b; i++)
#define FORD(i,a,b) for(int i = (a), _b = (b); i >= _b; i--)
#define REP(i,n) for(int i = 0, _n = (n); i < _n; i++)
#define REPD(i,n) for(int i = (n) - 1; i >= 0; i--)
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SIZE(c) (c).size()
#define RESET(c,x) memset(c,x,sizeof(c))
using namespace std;
typedef pair <int, int> PII;
typedef long long LL;
inline void OPEN(const string &s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
#define MAXV 100000
int V;
vector <int> G[MAXV + 5];
int dfs_low[MAXV + 5], dfs_num[MAXV + 5], dfs_parent[MAXV + 5];
int dfsNumberCounter, dfsRoot, rootChildren;
bool articulation_vertex[MAXV + 5];
int nBridge, nAp;
void articulationPointAndBridge(int u) {
dfs_low[u] = dfs_num[u] = dfsNumberCounter++;
REP (j, SIZE(G[u])) {
int v = G[u][j];
if (dfs_num[v] == -1) {
dfs_parent[v] = u;
if (u == dfsRoot) rootChildren++;
articulationPointAndBridge(v);
if (dfs_low[v] >= dfs_num[u])
articulation_vertex[u] = true;
if (dfs_low[v] > dfs_num[u])
++nBridge;
dfs_low[u] = min(dfs_low[u], dfs_low[v]);
} else if (v != dfs_parent[u])
dfs_low[u] = min(dfs_low[u], dfs_num[v]);
}
}
int main() {
scanf("%d", &V);
int m; scanf("%d", &m);
while (m--) {
int u, v; scanf("%d%d", &u, &v);
--u; --v;
G[u].PB(v);
G[v].PB(u);
}
dfsNumberCounter = 0; RESET(dfs_num, -1); RESET(dfs_low, 0);
RESET(dfs_parent, 0); RESET(articulation_vertex, 0);
REP (i, V) if (dfs_num[i] == -1) {
dfsRoot = i; rootChildren = 0;
articulationPointAndBridge(i);
articulation_vertex[dfsRoot] = (rootChildren > 1);
}
REP (i, V) if (articulation_vertex[i])
++nAp;
printf("%d %d\n", nAp, nBridge);
return 0;
}