Cod sursa(job #2120866)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 3 februarie 2018 00:21:39
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 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], t[N];
bool f[N];

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

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

static void anti_dfs(int u) {
	f[u] = true;
	cc.back().push_back(u);
	for (auto v: t[u]) if (!f[v])
		anti_dfs(v); }

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

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

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

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

	fo << cc.size() << '\n';
	for (auto &i: cc) {
		for (auto j: i)
			fo << j << ' ';
		fo << '\n'; }

	return 0; }