TJALG - Tìm TPLT mạnh

Tác giả: ladpro98

Ngôn ngữ: C++

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stdio.h>
#include <stack>
#define maxn 10004
#define maxm 100005
#define oo 123456789;

using namespace std;

int adj[maxm];
int head[maxn];
int linker[maxm];
int d[maxn];
int low[maxn];
bool avail[maxn];
stack<int> s;
int n, m, ssc, timer;

void init() {
    int x,y;
    //freopen("tjalg.in","r",stdin);
    scanf("%d %d", &n, &m);
    for(int i=1; i<=m; i++) {
        scanf("%d %d", &x, &y);
        adj[i] = y;
        linker[i] = head[x];
        head[x] = i;
    }
    for(int i=1; i<=n; i++)
        avail[i] = true;
    timer = 0;
    ssc = 0;
}

void dfs(int u) {
    timer++;
    d[u] = timer;
    low[u] = oo;
    s.push(u);
    int i = head[u];
    int v;
    while (i!=0) {
        v = adj[i];
        if (avail[v]) {
            if (d[v]>0)
                low[u] = min(low[u], d[v]);
            else {
                dfs(v);
                low[u] = min(low[u], low[v]);
            }
        }
        i = linker[i];
    }
    if (low[u]>=d[u]) {
        ssc++;
        do{
            v = s.top();
            avail[v] = false;
            s.pop();
        } while (v!=u);
    }
}

int main()
{
    init();
    for(int i=1; i<=n; i++)
        if (avail[i]) dfs(i);
    printf("%d",ssc);
    return 0;
}

Download