Cod sursa(job #2724700)

Utilizator mariamirabella2Bucur-Sabau Maria-Mirabela mariamirabella2 Data 17 martie 2021 18:12:44
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
stack <int> s;
int viz1[100005], viz2[100005],n,m,nr;
vector <int> v[100005],v2[100005],rasp[100005];
void dfs1(int nod){
	viz1[nod]=1;
	for(auto x: v[nod]){
		if(!viz1[x])
		{
			dfs1(x);
		}
	}
	s.push(nod);
}
void dfs2(int nod){
	viz2[nod]=1;
	for(auto x: v2[nod]){
		if(!viz2[x]){
			rasp[nr].push_back(x);
			dfs2(x);
			
		}
	}
}
int main()
{
	cin>>n>>m;
	int x,y;
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		v[x].push_back(y);
		v2[y].push_back(x);
	}
	for(int i=1;i<=n;i++){
		if(!viz1[i]){
			dfs1(i);
		}
	}
	while(!s.empty()){
		if(!viz2[s.top()]){
			nr++;
			rasp[nr].push_back(s.top());
			dfs2(s.top());
		}
		s.pop();
	}
	cout<<nr<<'\n';
	for(int i=1;i<=nr;i++){
		for(auto x: rasp[i]){
			cout<<x<<" ";
		}
		cout<<'\n';
	}
}