Cod sursa(job #2757347)

Utilizator GheorgheBBalamatiuc Gheorghe GheorgheB Data 5 iunie 2021 00:42:54
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

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

int n, m, nrctc;
vector<vector<int>> G, GT, ctc;
vector<int> v;
stack<int> s;

void read(){
	fin >> n;
	v = vector<int> (n + 1);
	G = GT = ctc = vector<vector<int>> (n + 1);
	for(fin >> m; m; m --){
		int x, y;
		fin >> x >> y;
		G[x].push_back(y);
		GT[y].push_back(x);
	}
}

void dfs(int k){
	v[k] = 1;
	for(auto x : G[k])
		if(!v[x])
			dfs(x);
	s.push(k);
}

void dfsT(int k){
	v[k] = 2;
	ctc[nrctc].push_back(k);
	for(auto x : GT[k])
		if(v[x] == 1)
			dfsT(x);
}

void solve(){
	for(int i = 1; i <= n; i ++)
		if(!v[i])
			dfs(i);
	while(!s.empty()){
		int k = s.top();
		s.pop();
		if(v[k] == 1)
			nrctc ++, dfsT(k);
	}
}

void print(){
	fout << nrctc << "\n";
	for(int i = 1; i <= nrctc; i ++, fout << "\n")
		for(auto x : ctc[i])
			fout << x << " ";
}

int main(){
	read();
	solve();
	print();
}