Cod sursa(job #2744504)

Utilizator gavra_bogdanBogdan Gavra gavra_bogdan Data 24 aprilie 2021 19:36:36
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <vector>
#include <cstring>

const int N = 1e5 + 5;

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

int k;
std::vector<int>l[N], g[N], cc[N], st;
bool viz[N];

void dfs(int node) {
	viz[node] = true;
	for(int to:l[node]) if(!viz[to]) dfs(to);
	st.push_back(node);
}

void dfs2(int node) {
	viz[node] = true;
	cc[k].push_back(node);
	for(int to:g[node]) if(!viz[to]) dfs2(to);
}

int main() {
	int n, m, from, to;
	fin>>n>>m;
	for(int i=1;i<=m;i++) {
		fin>>from>>to;
		l[from].push_back(to);
		g[to].push_back(from);
	}
	for(int i=1;i<=n;i++) if(!viz[i]) dfs(i);
	memset(viz, 0, sizeof(viz));
	while(st.size()) {
		int x = st.back();
		st.pop_back();
		if(!viz[x]) k++, dfs2(x);
	}
	fout<<k<<"\n";
	for(int i=1;i<=k;i++) {
		for(int x:cc[i]) fout<<x<<" ";
		fout<<"\n";
	}
}