Cod sursa(job #2722710)

Utilizator ViAlexVisan Alexandru ViAlex Data 13 martie 2021 11:16:25
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<cstring>
#include<map>
#include<algorithm>
#include<set>
#include<deque>
#include<queue>

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

const int mx=1e5+100;

int n,m;
bool vis[mx];
vector<int> g[mx],t[mx],q;

void read(){
	fin>>n>>m;
	int a,b;
	for(int i=0;i<m;i++){
		fin>>a>>b;
		g[a].push_back(b);
		t[b].push_back(a);
	}
}

void dfs1(int node){
	q.push_back(node);
	vis[node]=true;

	for(int k:g[node]){
		if(!vis[k]){
			dfs1(k);
		}
	}
}

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

void solve(){
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			dfs1(i);
		}
	}
	for(int i=1;i<=n;i++)
		vis[i]=false;

	vector<vector<int>> result;
	for(auto iter=q.rbegin();iter!=q.rend();iter++){
		int node=*iter;
		if(!vis[node]){
			result.emplace_back();
			dfs2(node,result.back());
		}
	}

	fout<<result.size()<<'\n';
	for(auto&comp:result){
		for(int node:comp){
			fout<<node<<" ";
		}
		fout<<'\n';
	}
}


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