Cod sursa(job #2488035)

Utilizator AndreiM.Andrei Moldoveanu AndreiM. Data 6 noiembrie 2019 00:11:41
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 kb
#include <iostream>
#include <vector>
#include <cstring>
#include <fstream>
//using namespace std;
#define NMAX 100005

//liste de adiacenta si transpusa
std::vector<int> v[NMAX], vT[NMAX];

//vec comp conexe
std::vector<std::vector<int>> vecCon;

std::vector<int> H;

//vector vizita
int uz[NMAX];

//nr de noduri
int n;

void Citire(void);
void Afisare(void);
void DFS(int);
void DFST(int);

int main()
{
	Citire();
	for (int i = 1; i <= n; i++)
		if (!uz[i]) DFS(i);

	memset(uz, 0, sizeof(uz));
	for (int i = H.size()-1; i>= 0; i--)
		if (!uz[H[i]])
		{
			vecCon.push_back(std::vector<int>());
			DFST(H[i]);
		}

	Afisare();

	return 0;
}

void Citire()
{
	std::fstream fin("ctc.in");
	int m;
	int a, b;
	fin >> n >> m;
	//aloc memorie pentru fiecare varf
	for (int i = 1; i <= m; i++)
	{
		fin >> a >> b;
		v[a].push_back(b);
		vT[b].push_back(a);
	}
}

void Afisare()
{
	std::ofstream fout("ctc.out");
	fout << vecCon.size() << std::endl;
	for (std::vector<std::vector<int>>::iterator it = vecCon.begin(); it != vecCon.end(); ++it)
	{
		for (std::vector<int>::iterator it2 = it->begin(); it2 != it->end(); ++it2)
			fout << *it2 << ' ';
		fout << std::endl;
	}
	fout.close();
}

void DFS(int nod)
{
	uz[nod] = 1;
	for (std::vector<int>::iterator it = v[nod].begin(); it != v[nod].end(); ++it)
	{
		if (!uz[*it]) DFS(*it);
	}
	H.push_back(nod);
}

void DFST(int nod)
{
	uz[nod] = 1;
	for (std::vector<int>::iterator it = vT[nod].begin(); it != vT[nod].end(); ++it)
	{
		if (!uz[*it]) DFST(*it);
	}
	vecCon.back().push_back(nod);
}