Cod sursa(job #2190838)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 31 martie 2018 20:30:06
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <bits/stdc++.h>
using namespace std;

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

const int N = 1e5 + 5;

vector<int> g[N], tg[N];
bool f[N];

vector<vector<int>> ctc;
vector<int> top;
int n, m, p;

static void dfs1(int u) {
	f[u] = true;
	for (auto v: g[u]) if (!f[v])
		dfs1(v);
	top.push_back(u); }

static void dfs2(int u) {
	f[u] = true;
	ctc.back().push_back(u);
	for (auto v: tg[u]) if (!f[v])
		dfs2(v); }

int main() {
	fi >> n >> m;
	for (int a, b, i = 0; i < m; ++i) {
		fi >> a >> b;
		g[a].push_back(b);
		tg[b].push_back(a); }

	for (int u = 1; u <= n; ++u) if (!f[u])
		dfs1(u);

	memset(f, 0x00, sizeof f);
	reverse(begin(top), end(top));

	for (auto u: top) if (!f[u]) {
		p+= 1;
		ctc.emplace_back();
		dfs2(u); }

	fo << ctc.size() << '\n';
	for (const auto &c: ctc) {
		for (const auto &j: c)
			fo << j << ' ';
		fo << '\n'; }

	return 0; }