Cod sursa(job #2712403)

Utilizator Mihai180315Mihai Smarandache Mihai180315 Data 25 februarie 2021 18:50:12
Problema Componente tare conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;
const int nmax = 100000;

vector <int> g[nmax], gt[nmax], compConexe[nmax];
stack <int> st;
int viz[nmax], nrComp;

void DFS1(int nod)
{
	viz[nod] = 1;
	for (int i = 0; i < g[nod].size(); ++i) {
		int aux = g[nod][i];
		if (viz[aux] == 0) {
			DFS1(aux);
		}
	}
	st.push(nod);
}

void DFS2(int nod)
{
	viz[nod] = 2;
	compConexe[nrComp].push_back(nod);
	for (int i = 0; i < gt[nod].size(); ++i) {
		int aux = gt[nod][i];
		if (viz[aux] == 1) {
			DFS2(aux);
		}
	}
}

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

	int n, m;
	int x, y;
	fin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		fin >> x >> y;
		g[x].push_back(y);
		gt[y].push_back(x);
	}

	for (int i = 1; i <= n; ++i) {
		if (viz[i] == 0) {
			DFS1(i);
		}
	}
	while (!st.empty()) {
		int nod = st.top();
		if (viz[nod] == 1) {
			++nrComp;
			DFS2(nod);
		}
		st.pop();
	}

	for (int i = 1; i <= nrComp; ++i) {
		sort(compConexe[i].begin(), compConexe[i].end());
	}
	fout << nrComp << "\n";
	for (int i = 1; i <= nrComp; ++i) {
		for (int j = 0; j < compConexe[i].size(); ++j) {
			fout << compConexe[i][j] << " ";
		}
		fout << "\n";
	}
	fin.close();
	return 0;
}