Cod sursa(job #3309087)

Utilizator ViAlexVisan Alexandru ViAlex Data 31 august 2025 21:06:11
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;

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

vector<vector<int>> graph;
vector<vector<int>> tgraph;
vector<bool> visited;
int n, m;


void read(){
	in>>n>>m;
	graph.resize(n);
	tgraph.resize(n);
	visited.resize(n);
	int a, b;
	for (int i=0;i<m;i++){
		in>>a>>b;
		graph[a-1].push_back(b-1);
		tgraph[b-1].push_back(a-1);
	}
}

void dfs1(int node, vector<int>& topological) {
	visited[node] = true;
	for(int k: graph[node]) {
		if (!visited[k]) {
			dfs1(k, topological);
		}
	}
	topological.push_back(node);
}

void dfs2(int node, vector<int>&comp){
	comp.push_back(node);
	visited[node] = true;
	for(int k: tgraph[node]) {
		if (!visited[k]) {
			dfs2(k, comp);
		}
	}
}


void solve() {
	vector<int> topological;
	for (int i=0;i<n;i++){
		if(!visited[i]) {
			dfs1(i, topological);
		}
	}

	visited = vector<bool>(n, false);
	vector<vector<int>> components;

	for(auto iter = topological.rbegin(); iter!=topological.rend(); iter++){
		int here = *iter;
		if (!visited[here]) {
			vector<int> component;
			dfs2(here, component);
			components.push_back(move(component));
		}
	}

	out<<components.size()<<endl;
	for(const auto&c: components) {
		for(int node: c){
			out<<node+1<<" ";
		}
		out<<'\n';
	}
}

int main(){
	read();
	solve();
	return 0;
}