Cod sursa(job #3229155)

Utilizator luc3lexaAlexandrescu Luca luc3lexa Data 14 mai 2024 09:23:46
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

const int nmax = 1e5+10;
int n,m,numar;
vector<vector<int>> mat1(nmax),mat2(nmax),ans(nmax);
vector<int> visited(nmax),noduri;

void read_input(){
	fin >> n >> m;
	int nod_1,nod_2;
	for(int i = 1;i <=m; i++){
		fin >> nod_1 >> nod_2;
		mat1[nod_1].push_back(nod_2);
		mat2[nod_2].push_back(nod_1);
	}
};
void dfs1(int nod){
	visited[nod] = 1;
	for(auto nod_aux : mat1[nod]){
		if(!visited[nod_aux]){
			dfs1(nod_aux);
		}
	};
	noduri.push_back(nod);
};
void solve1(){
	for(int i = 1; i <=n; i++){
		if(!visited[i]){
			dfs1(i);
		}
	}
};
void dfs2(int nod,int numar){
	visited[nod] = 1;
	for(auto nod_aux : mat2[nod]){
		if(!visited[nod_aux]){
		    ans[numar].push_back(nod_aux);
			dfs2(nod_aux,numar);
		}
	}
};
void solve2(){
	reverse(noduri.begin(),noduri.end());
	fill(visited.begin(),visited.end(),0);
	numar = 0;
	for(auto i : noduri){
		if(!visited[i]){
			numar++;
			ans[numar].push_back(i);
			dfs2(i,numar);
		}
	};
	fout << numar << '\n';
	for(int i = 1; i <=numar; i++,fout << '\n'){
	    sort(ans[i].begin(),ans[i].end());
		for(auto x : ans[i]){
			fout << x << " ";
		}
	}
}
int main(){
	read_input();
	solve1();
	solve2();
	return 0;
}