Cod sursa(job #2722349)

Utilizator xCata02Catalin Brita xCata02 Data 12 martie 2021 19:26:18
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda no-time-rest-v3 Marime 1.33 kb
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ld long double
#define endl "\n"
 
const int Nmax = 100010;
const int MODULO = 1e9 + 7;
const int oo = -1e9;

vector < int > g[Nmax];
vector < int > t[Nmax];
vector < int > sol[Nmax];

stack < int > stk;
int componenta = 0;
bool viz[Nmax];

void DFS(int nod) {
	viz[nod] = 1;
	for(auto it: g[nod]) {
		if(viz[it] == 0 ) {
			DFS(it);
		}
	}
	stk.push(nod);
}

void dfs(int nod) {
	sol[componenta].push_back(nod);
	viz[nod] = 0;
	for(auto it: t[nod]) {
		if(viz[it] == 1) {
			dfs(it);
		}
	}
}

void solve() {
	int n, m; cin >> n >> m;
	while(m--) {
		int x, y; cin >> x >> y;
		g[x].push_back(y);
		t[y].push_back(x);
	}

	for(int i = 1; i <= n; i++) {
		if(viz[i] == 0) {
			DFS(i);
		}
	}

	while(!stk.empty()) {
		int nod = stk.top(); stk.pop();
		if(viz[nod] == 1) {
			componenta++;
			dfs(nod);
		}
	}

	cout << componenta << endl;
	for(int i = 1; i <= n; i++) {
		for(auto it : sol[i]) {
			cout << it << " ";
		}
		cout << endl;
	}

}
	
void fisier() {
	freopen("ctc.in" , "r", stdin);
	freopen("ctc.out", "w", stdout);
}

 
int main() {
	ios_base::sync_with_stdio(0);
 
	cin .tie(0);
	cout.tie(0);

	fisier();
 
	int testCases = 1;
	//cin >> testCases;
	while(testCases--) {
		solve();
	}
}