Cod sursa(job #3367617)

Utilizator Radu_BicliBiclineru Radu Radu_Bicli Data 8 octombrie 2026 23:43:18
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <bits/stdc++.h>
//#include <bits/extc++.h>

using namespace std;
	
#define USE_STD_IO 0
#if USE_STD_IO
    #define fin cin
    #define fout cout
#else
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");
#endif // USE_STD_IO

int n, m, i;
vector<int> gr[2][100002];
vector<vector<int>> v;
bool viz[100002];

stack<int> stiv;

static inline void DFSNorm(const int nod) {
	viz[nod] = true;
	//cout << "1 " << nod << "\n";
	for(const int urm : gr[0][nod]) {
		if(false == viz[urm]) DFSNorm(urm);
	}
	stiv.push(nod);
}

static inline void DFSInv(const int nod) {
	v.back().push_back(nod);
	viz[nod] = false;
	//cout << "2 " << nod << "\n";
	for(const int urm : gr[1][nod]) {
		if(true == viz[urm]) DFSInv(urm);
	}
}

int main() {
    #if USE_STD_IO
        ios_base::sync_with_stdio(false);
    #endif // USE_STD_IO
    fin.tie(NULL);
    fout.tie(NULL);

	fin >> n >> m;
	for(i = 1; i <= m; i++) {
		int x, y;
		fin >> x >> y;
		gr[0][x].push_back(y);
		gr[1][y].push_back(x);
	}
	for(i = 1; i <= n; i++) {
		if(false == viz[i]) DFSNorm(i);
	}
	while(false == stiv.empty()) {
		if(true == viz[stiv.top()]) {
			v.push_back({});
			DFSInv(stiv.top());
		}
		stiv.pop();
	}
	fout << v.size() << '\n';
	for(const vector<int>& comp : v) {
		for(const int nod : comp) fout << nod << ' ';
		fout << '\n';
	}
	
    return 0;
}