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;
}

Download