Cod sursa(job #2758935)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 14 iunie 2021 14:22:07
Problema Componente tare conexe Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

const int N = 1e5 + 5;

vector<int> g[N];
int f[N];

vector<vector<int>> ctc;
vector<int> ord;
int n, m;

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

void dfs2(int u) {
	ctc.back().emplace_back(u);
	f[u] = 2;
	for (auto v: g[u]) if (f[v] != 2)
		dfs2(v);
}


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

	ord.reserve(n);
	for (int i = 1; i <= n; ++i)
		if (!f[i])
			dfs(i);


//	for (auto i: ord)
//		cerr << i << ' ';
//	cerr << endl;

	for (int i = 0; i < n; ++i) if (f[ord[i]] != 2) {
		ctc.emplace_back();
		dfs2(ord[i]);
	}


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

	return 0;
}