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