TJALG - Tìm TPLT mạnh
Tác giả: skyvn97
Ngôn ngữ: C++
#include<cstdio>
#include<vector>
#define MAX 10101
using namespace std;
int n,m,cnt,r;
vector<int> g[MAX];
int num[MAX];
int low[MAX];
bool fre[MAX];
struct stack {
int st[MAX];
int size;
stack(){
size=0;
}
bool empty(void) {
return (size==0);
}
void push(int x) {
size++;
st[size]=x;
}
int pop(void) {
size--;
return (st[size+1]);
}
};
int min(int x,int y) {
if (x<y) return x; else return y;
}
stack s;
void loadgraph(void) {
scanf("%d",&n);
scanf("%d",&m);
int i,u,v;
for (i=1;i<=m;i=i+1) {
scanf("%d",&u);
scanf("%d",&v);
g[u].push_back(v);
}
for (i=1;i<=n;i=i+1) {
fre[i]=true;
num[i]=0;
}
cnt=0;
s=stack();
}
void visit(int u) {
int i,v;
cnt++;
num[u]=cnt;
low[u]=cnt;
s.push(u);
for (i=0;i<g[u].size();i=i+1) {
v=g[u][i];
if (fre[v]) {
if (num[v]>0) low[u]=min(low[u],num[v]);
else {
visit(v);
low[u]=min(low[u],low[v]);
}
}
}
if (low[u]==num[u]) {
r=r+1;
while (!s.empty()) {
v=s.pop();
fre[v]=false;
if (v==u) break;
}
}
}
void process(void) {
int i;
r=0;
for (i=1;i<=n;i=i+1)
if (num[i]==0) visit(i);
printf("%d",r);
//exit(0);
}
int main(void) {
loadgraph();
process();
return 0;
}