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;
}