Cod sursa(job #1956948)

Utilizator flibiaVisanu Cristian flibia Data 7 aprilie 2017 10:24:47
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <bits/stdc++.h>
#define pb push_back

using namespace std;

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

int n, m, st[100100], k, cnt, x, y; bool viz[100100];
vector <int> v[100100], vv[100100], sol[100100];

void dfs(int x){
	viz[x] = 1;
	for(auto it : v[x])
		if(!viz[it]) dfs(it);
	st[++k] = x;
}

void dive(int x){
	viz[x] = 1;
	sol[cnt].pb(x);
	for(auto it : vv[x])
		if(!viz[it]) dive(it);
}

int main(){
	in >> n >> m;
	for(int i = 1; i <= m; i++){
		in >> x >> y;
		v[x].pb(y);
		vv[y].pb(x);
	}	
	for(int i = 1; i <= n; i++)
		if(!viz[i]) dfs(i);
	memset(viz, 0, sizeof(viz));
	for(; k; k--) 
		if(!viz[st[k]]){
			cnt++;
			dive(st[k]);
		}
	out << cnt << '\n';
	for(int i = 1; i <= cnt; i++){
		for(auto it : sol[i]) out << it << ' ';
		out << '\n';
	}
	return 0;
}