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

Download