let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

MESSAGE - Truyền tin

solution.md

Bài này ta tìm tất cả các thành phần liên thông mạnh, sau đó đếm số thành phần mà không có cạnh đi vào.

Code ở dưới tìm thành phần liên thông mạnh và hợp nhất tất cả các đỉnh cùng chung một TPLT mạnh lại bằng Disjoint Set.

main.cpp
Open in Github Download
#include <vector>
#include <iostream>
using namespace std;

typedef vector<vector<int>> dsk;

int cha[800];
int find(int u) {
    if (cha[u] != u) cha[u] = find(cha[u]);
    return cha[u];
}

vector<int> stack;
bool visited[800], instack[800];

void dfs(int u, dsk &ke) {
    visited[u] = true;
    instack[u] = true;
    stack.push_back(u);
    for (int v: ke[u]) if (instack[v]) {
        v = find(v);
        while (stack.back() != v) {
            cha[stack.back()] = v;
            stack.pop_back();
        }
    }
    for (int v: ke[u]) if (!visited[v]) dfs(v, ke);
    instack[u] = false;
    if (stack.back() == u) stack.pop_back();
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m; cin >> n >> m;
    dsk ke(n);
    while (m--) {
        int u, v; cin >> u >> v;
        ke[u-1].push_back(v-1);
    }
    for (int i=0; i<n; i++) cha[i] = i;
    for (int i=0; i<n; i++) if (!visited[i]) dfs(i, ke);

    vector<int> f(n, 0);
    for (int i=0; i<n; i++) f[i] = (cha[i] == i);
    for (int i=0; i<n; i++) {
        for (int j: ke[i]) {
            if (find(i) != find(j)) f[find(j)] = 0;
        }
    }
    int res = 0;
    for (int i=0; i<n; i++) res += f[i];
    cout << res;
    return 0;
}
Comments