Cod sursa(job #3212054)

Utilizator vladdobro07vladdd vladdobro07 Data 11 martie 2024 00:02:09
Problema Componente tare conexe Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <bits/stdc++.h>
#define pb push_back
#define all(v) v.begin(),v.end()

using namespace std;

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

const int nmax = 1e5;

vector<vector<int>> ctc;
vector<int> edge[nmax + 1], egde[nmax + 1];
vector<bool> viz(nmax + 1, 0);
vector<int> topo(1, 0);

int n, m, x, y;

void read() {
	fin >> n >> m;

	for(int i = 1; i <= m; i++) {
		fin >> x >> y;
		edge[x].pb(y);
		egde[y].pb(x);
	}
}

void dfs(int nod) {
	viz[nod] = 1;

	for(int fiul : edge[nod]) {
		if(viz[fiul] == 0)
			dfs(fiul);
	}
	topo.pb(nod);
}

void sfd(int nod) {
	viz[nod] = 1;
	ctc.back().pb(nod);

	for(int fiul : edge[nod]) {
		if(viz[fiul] == 0)
			sfd(fiul);
	}
}

void print() {
	fout << ctc.size() << "\n";
	for(int cur = 0; cur < ctc.size(); cur++) {
		for(auto val : ctc[cur])
			fout << val << " ";
		fout << "\n";
	}
}

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

	viz = vector<bool>(nmax + 1, 0);
	for(int i = 1; i <= n; i++) {
		int cur = topo[i];

		if(viz[cur] == 0) {
			ctc.pb(vector<int>());
			sfd(cur);
		}
	}
}

int main() {
	read();
	comp_ctc();
	print();
	return 0;
}