Cod sursa(job #2969555)

Utilizator ViAlexVisan Alexandru ViAlex Data 23 ianuarie 2023 13:42:41
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include<iostream>
#include<deque>
#include<algorithm>
#include<vector>
#include<fstream>
using namespace std;

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

const int mx = 100001;

int n,m;
vector<int> g[mx],gt[mx];
vector<int> sorted;
vector<bool> visited;

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

void dfs1(int node){
	visited[node] = true;	
	for(int k:gt[node]){
		if(!visited[k])
			dfs1(k);
	}
	sorted.push_back(node);
}

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

void solve(){
	for(int i=1;i<=n;i++){
		if(!visited[i])
			dfs1(i);
	}	
	visited.assign(n+1,false);
	int cnt = 0;
	for(auto x = sorted.rbegin();x!=sorted.rend();x++){
		int p = *x;
		if(!visited[p]){
			dfs2(p);
			cnt++;
		}
	}
	out<<cnt<<'\n';
	visited.assign(n+1,false);
	for(auto x = sorted.rbegin();x!=sorted.rend();x++){
		int p = *x;
		if(!visited[p]){
			vector<int> comp;
			dfs3(p,comp);
			for(int x:comp)
				out<<x<<" ";
			out<<'\n';
		}
	}
}



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