TJALG - Tìm TPLT mạnh

Tác giả: happyboy99x

Ngôn ngữ: C++

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define sz(a) int((a).size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); it != _e; ++it)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000
#define N

vvi g; //graph
vii e; //edge e[i].first = e[i].lowlink, e[i].second = e[i].index
int n, m, idx, res;
bool inS[10005];
stack<int> s;

void dfs(int u) {
	e[u].fi = e[u].se = idx++;
	inS[u] = 1; s.push(u);
	tr(g[u],it)
		if( e[*it].se == -1 ) {
			dfs(*it); 
			e[u].fi = min( e[u].fi, e[*it].fi );
		} else if( inS[*it] ) e[u].fi = min( e[u].fi, e[*it].se );
	if( e[u].fi == e[u].se ) {
		++res; int v;
		do {
			v = s.top(); s.pop();
			inS[v] = 0;
		} while( u != v );
	}
}

int main() {
	scanf( "%d%d", &n, &m );
	g = vvi(n, vi()); e = vii(n, ii(-1,-1));
	rep(i,m) {
		int u, v; scanf( "%d%d", &u, &v );
		g[--u].push_back(--v);
	}
	rep(i,n) if(e[i].se == -1) dfs(i);
	printf( "%d\n", res );
	return 0;
}

Download