Cod sursa(job #3240369)

Utilizator CosminaneBoac Mihai Cosmin Cosminane Data 14 august 2024 14:55:18
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <vector>
using namespace std;
vector <int> v[100005], vr[100005], st, comp;
vector <vector <int>> r;
int f[100005];
void dfs(int x) {
	int i;
	f[x] = 1;
	for (i = 0; i < v[x].size(); i++) {
		if (f[v[x][i]] == 0) {
			dfs( v[x][i]);
		}
	}
	st.push_back( x );
}
void dfsr(int x) {
	int i;
	f[x] = 2;
	comp.push_back( x );
	for (i = 0; i < vr[x].size(); i++) {
		if (f[vr[x][i]] == 1) {
			dfsr( vr[x][i]);
		}
	}
}
int main() {
	int n, m, i, j, x, y;
	ifstream fin( "ctc.in" );
	ofstream fout( "ctc.out");
	fin >> n >> m;
	for (i = 0; i < m; i++) {
		fin >> x >> y;
		v[x].push_back( y );
		vr[y].push_back( x );
	}
	for (i = 1; i <= n; i++) {
		if (f[i] == 0) {
			dfs( i );
		}
	}
	for (i = n - 1; i >= 0; i--) {
		if (f[st[i]] == 1) {
			dfsr( st[i]);
			r.push_back( comp );
			comp.clear();
		}
	}
	fout << r.size() << '\n';
	for (i = 0; i < r.size(); i++) {
		for (j = 0; j < r[i].size(); j++) {
			fout << r[i][j] << ' ';
		}
		fout << '\n';
	}
	return 0;
}