Tìm khớp và cầu
Bài toán
Đếm số lượng khớp và cầu trên đồ thị vô hướng.
Độ phức tạp
O(n+m)
Code này của Nguyễn Tiến Trung Kiên
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int N = 100005;
int n, m;
vector<int> a[N];
int CriticalEdge = 0;
bool CriticalNode[N];
int Num[N], Low[N], Time = 0;
void visit(int u, int p) {
int NumChild = 0;
Low[u] = Num[u] = ++Time;
for (int v : a[u])
if (v != p) {
if (Num[v] != 0)
Low[u] = min(Low[u], Num[v]);
else {
visit(v, u);
NumChild++;
Low[u] = min(Low[u], Low[v]);
if (Low[v] >= Num[v])
CriticalEdge++;
if (u == p) {
if (NumChild >= 2)
CriticalNode[u] = true;
} else {
if (Low[v] >= Num[u])
CriticalNode[u] = true;
}
}
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int x, y;
scanf("%d%d", &x, &y);
a[x].push_back(y);
a[y].push_back(x);
}
for (int i = 1; i <= n; i++)
if (!Num[i]) visit(i, i);
int Count = 0;
for (int i = 1; i <= n; i++)
if (CriticalNode[i]) Count++;
printf("%d %d\n", Count, CriticalEdge);
}
Nhận xét
Code này đã được dùng để nộp cho một bài trên SPOJ
Tham khảo
http://vn.spoj.com/problems/GRAPH_/
https://codeforces.com/group/FLVn1Sc504/contest/274814/problem/F
Mô tả
int Num[]
Num[u] là thời gian bắt đầu thăm nút u
int Low[]
giả sử, từ nút u, dùng các cung trên cây DFS (các cung một chiều từ cha xuống con), và tối đa một cung ngược, nút thấp nhất (nút có Num bé nhất) mà ta thăm được là v thì Low[u] = Num[v]
Đánh giá
Các bạn có thể đánh giá bài viết, yêu cầu giải thích, hoặc gửi nhận xét tại đây.
http://goo.gl/forms/tZ7OJQTSaa