Cod sursa(job #2740153)

Utilizator StefanSanStanescu Stefan StefanSan Data 11 aprilie 2021 18:20:25
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include      <iostream>
#include      <fstream>
#include      <algorithm>
#include      <vector>
#include      <stack>

#define MAX 100005

using namespace std;

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

int n, m, viz[MAX], nr_CTC;

vector < int >G[MAX], GT[MAX], Rezultate[MAX];
stack < int > S;

void dfs(int nod) {
	viz[nod] = 1;
	for (unsigned int i = 0; i < G[nod].size(); i++)
		if (!viz[G[nod][i]]) dfs(G[nod][i]);

	S.push(nod);
}

void dfs_T(int nod) {
	viz[nod] = 2;
	Rezultate[nr_CTC].push_back(nod);
	for (unsigned int i = 0; i < GT[nod].size(); i++)
		if (viz[GT[nod][i]] == 1) dfs_T(GT[nod][i]);
}

int main() {

	ios::sync_with_stdio(false);
	in.tie(NULL), out.tie(NULL);

	in >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y;
		in >> x >> y;
		G[x].push_back(y);
		GT[y].push_back(x);
	}

	for (int i = 1; i <= n; i++)
		if (!viz[i]) dfs(i);

	while (!S.empty()) {
		int nod = S.top();
		if (viz[nod] == 1) {
			nr_CTC++;
			dfs_T(nod);
		}
		S.pop();
	}

	out << nr_CTC << '\n';
	for (int i = 1; i <= nr_CTC; i++) {
		for (unsigned int j = 0; j < Rezultate[i].size(); j++) {
			out << Rezultate[i][j] << ' ';
		}
		out << '\n';
	}

	return 0;
}