Cod sursa(job #2425442)

Utilizator flibiaVisanu Cristian flibia Data 24 mai 2019 20:22:47
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("ctc.in");
ofstream out("ctc.out");

int n, m, x, y, viz[100100], st[100100], vf, cnt;
vector<int> v[100100], vv[100100], sol[100100];

int dfs(int x) {
	viz[x] = 1;
	for (auto y : v[x])
		if (!viz[y])
			dfs(y);
	st[++vf] = x;
}

void dfs2(int x) {
	viz[x] = 0;
	sol[cnt].push_back(x);
	for (auto y : vv[x])
		if (viz[y])
			dfs2(y);
}

int main() {
	in >> n >> m;
	for (int i = 1; i <= m; i++) {
		in >> x >> y;
		v[x].push_back(y);
		vv[y].push_back(x);
	}
	
	for (int i = 1; i <= n; i++)
		if (!viz[i])
			dfs(i);
			
	for (; vf; vf--)
		if (viz[st[vf]]) {
			cnt++;
			dfs2(st[vf]);
		}
		
	out << cnt << '\n';
	for (int i = 1; i <= cnt; i++, out << '\n')
		for (auto it : sol[i])
			out << it << ' ';
	return 0;
}