Cod sursa(job #2754662)

Utilizator vlad082002Ciocoiu Vlad vlad082002 Data 26 mai 2021 11:27:54
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <bits/stdc++.h>
using namespace std;

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

int n, m;
vector<int> g[100005], gt[100005];
vector<vector<int> > ctc;
vector<int> sorted;
bool v[100005];

void dfs1(int x) {
	v[x] = true;
	for(auto next: g[x])
		if(!v[next])
			dfs1(next);
	sorted.push_back(x);
}

void dfs2(int x) {
	v[x] = true;
	ctc.back().push_back(x);
	for(auto next: gt[x])
		if(!v[next])
			dfs2(next);
}

int main() {
	fin >> n >> m;
	while(m--) {
		int a, b;
		fin >> a >> b;
		g[a].push_back(b);
		gt[b].push_back(a);
	}
	for(int i = 1; i <= n; i++)
		if(!v[i])
			dfs1(i);
	for(int i = 1; i <= n; i++) v[i] = false;
	for(int i = sorted.size()-1; i >= 0; i--) {
		if(!v[sorted[i]]) {
			ctc.push_back({});
			dfs2(sorted[i]);
		}
	}

	fout << ctc.size() << '\n';
	for(auto x: ctc) {
		for(auto y: x) fout << y << ' ';
		fout << '\n';
	}
}