tarzan.cpp (2)

Bài toán

Đếm số thành phần liên thông mạnh không có cung ra.

Độ phức tạp

thời gian: O(n+m)

bộ nhớ phụ: O(n)

Code này của Nguyễn Tiến Trung Kiên

#include <stdio.h>

#include <iostream>

#include <stack>

#include <vector>

using namespace std;

#define N 100005

#define oo 0x3c3c3c3c

int n, m;

vector<int> a[N];

int Num[N], Low[N], cnt = 0;

stack<int> st;

int Count = 0;

void minimize(int &a, int b) {

    if (a > b) a = b;

}

void visit(int u) {

    Num[u] = Low[u] = ++cnt;

    st.push(u);

    for (int v : a[u])

        if (Num[v])

            minimize(Low[u], Num[v]);

        else {

            visit(v);

            minimize(Low[u], Low[v]);

        }

    if (Num[u] == Low[u]) {

        int v;

        do {

            v = st.top();

            st.pop();

            Num[v] = Low[v] = -oo;

        } while (v != u);

        Count++;

    }

}

int main() {

    scanf("%d%d", &n, &m);

    for (int i = 1; i <= m; i++) {

        int x, y;

        scanf("%d%d", &x, &y);

        a[y].push_back(x);  // WARNING: reversed edge

    }

    for (int i = 1; i <= n; ++i) if (!Num[i]) visit(i);

    printf("%d\n", Count);

}

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/MESSAGE/

https://codeforces.com/group/FLVn1Sc504/contest/274506/problem/F