Cod sursa(job #1438901)

Utilizator VladutZ94FMI Chichirau Vlad Vasile VladutZ94 Data 21 mai 2015 02:45:19
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <fstream>
#include <vector>
#define NMAX 200001

std::vector<int>graf[NMAX];
std::vector<int>graf_t[NMAX];
std::vector<int>solutie[NMAX];
int n, m;
int index[NMAX], ordine[NMAX];
int k, h;

void DFS(int nod)
{
	solutie[h].push_back(nod);
	index[nod] = 1;
	for (int i = 0; i < graf[nod].size(); i++)
	{
		if (index[graf[nod][i]] == 0)
		{
			DFS(graf[nod][i]);
		}
	}
}

void DFST(int nod)
{
	index[nod] = 1;
	for (int i = 0; i < graf_t[nod].size(); i++)
	{
		if (index[graf_t[nod][i]] == 0)
		{
			DFST(graf_t[nod][i]);
		}
	}
	k++;
	ordine[k] = nod;
}

void citire()
{
	std::ifstream f("ctc.in");
	f >> n >> m;
	int x, y;
	for (int i = 1; i <= m; i++)
	{
		f >> x >> y;
		graf[x].push_back(y);
		graf_t[y].push_back(x);
	}
}

int main()
{
	citire();
	for (int i = 1; i <= n; i++)
	{
		if (index[i] == 0)
		{
			DFST(i);
		}
	}
	for (int i = 1; i <= n; i++)
	{
		index[i] = 0;
	}
	for (int i = n; i >= 1; i--)
	{
		if (index[ordine[i]] == 0)
		{
			h++;
			DFS(ordine[i]);
		}
	}

	std::ofstream g("ctc.out");
	g << h << "\n";
	for (int i = h; i >=1 ; i--)
	{
		for (int j = 0; j < solutie[i].size(); j++)
		{
			g << solutie[i][j] << " ";
		}
		g << "\n";
	}
	return 0;
}