Cod sursa(job #2410206)

Utilizator LucaSeriSeritan Luca LucaSeri Data 19 aprilie 2019 20:04:19
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <bits/stdc++.h>
 
using namespace std;

const int MAXN = 1e5 + 10;

vector< int > gr[MAXN];
vector< int > gri[MAXN];
int cnt = 0;
vector< int > nodes[MAXN];

int viz[MAXN];

vector< int > v;

void dfs1(int node) {
	viz[node] = 1;
	for(auto &x : gr[node]) if(!viz[x]) dfs1(x);

	v.emplace_back(node);
}

void dfs2(int node) {
	viz[node] = 0;
	nodes[cnt].emplace_back(node);
	for(auto &x : gri[node]) if(viz[x]) dfs2(x);
}
int main() {
	#ifdef BLAT
		freopen("input", "r", stdin);
	#else
		freopen("ctc.in", "r", stdin);
		freopen("ctc.out", "w", stdout);
	#endif
 
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n, m;
	cin >> n >> m;

	for(int i = 1; i <= m; ++i) {
		int a, b;
		cin >> a >> b;
		gr[a].emplace_back(b);
		gri[b].emplace_back(a);
	}

	for(int i = 1; i <= n; ++i) {
		if(!viz[i]) {
			dfs1(i);
		}
	}

	reverse(v.begin(), v.end());
	for(auto &x : v) {
		if(viz[x]) {
			++cnt;
			dfs2(x);
		}
	}

	cout << cnt << '\n';

	for(int i = 1; i <= cnt; ++i) {
		sort(nodes[i].begin(), nodes[i].end());
		for(auto &x : nodes[i]) cout << x << ' ';

		cout << '\n';
	}
	return 0;
}