Cod sursa(job #2932654)

Utilizator namesurname01Name Surname namesurname01 Data 3 noiembrie 2022 16:26:41
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <vector>
#include <deque>

using namespace std;

#define N 100001

vector<int> graph[N], graphT[N], solution[N];
bool viz[N];
deque<int> deq;
deque<int> :: reverse_iterator it;

int ctc;

void topo(int node) {
	viz[node] = 1; //frecventa o fac sa verific nodurile inserate in coada
	for (int i = 0; i < graph[node].size(); ++i) {
		if (!viz[graph[node][i]]) {
			topo(graph[node][i]);
		}
	}
	deq.push_back(node);
}

void dfs(int node) {
	viz[node]= 1;
	solution[ctc].push_back(node);
	for (int i = 0; i < graphT[node].size(); ++i) {
		if (!viz[graphT[node][i]]) {
			dfs(graphT[node][i]);
		}
	}
}

int main() {
	ifstream f("ctc.in");
	ofstream g("ctc.out");
	int nodes, arcs, a, b;
	f >> nodes >> arcs;
	for (int i = 1; i <= arcs; ++i) {
		f >> a >> b;
		graph[a].push_back(b);
		graphT[b].push_back(a);
	}
	for (int i = 1; i <= nodes; ++i) {
		if (!viz[i]) {
			topo(i);
		}
	}

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

	for (it = deq.rbegin(); it != deq.rend(); ++it) {
		int value = *it;
		if (!viz[value]) {
			++ctc;
			dfs(value);
		}
	}

	g << ctc << "\n";
	for (int i = 1; i <= ctc; ++i) {
		while (!solution[i].empty()) {
			g << solution[i].back() << " ";
			solution[i].pop_back();
		}
		g << "\n";
	}
	f.close();
	g.close();
	return 0;
}