Cod sursa(job #1260511)

Utilizator pulseOvidiu Giorgi pulse Data 11 noiembrie 2014 13:07:40
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

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

int N, M;
int nrCTC;
vector <int> G[MAXN], Gt[MAXN], Res[MAXN];
stack <int> S;
bool Used[MAXN];

void DFS(int node)
{
	Used[node] = 1;
	for (vector <int> :: iterator it = G[node].begin(); it != G[node].end(); ++it)
	{
		int v = *it;
		if (!Used[v])
			DFS(v);
	}
	S.push(node);
}

void DFSt(int node)
{
	Res[nrCTC].push_back(node);
	Used[node] = 1;
	for (vector <int> :: iterator it = Gt[node].begin(); it != Gt[node].end(); ++it)
	{
		int v = *it;
		if (!Used[v])
			DFSt(v);
	}
}

void Componente_Tare_Conexe()
{
	for (int i = 1; i <= N; ++i)
		if (!Used[i])
			DFS(i);
	for (int i = 1; i <= N; ++i)
		Used[i] = 0;
	while (!S.empty())
	{
		int node = S.top();
		if (!Used[node])
		{
			++nrCTC;
			DFSt(node);
		}
		S.pop();
	}
	fout << nrCTC << '\n';
	for (int i = 1; i <= nrCTC; ++i)
	{
		for (int j = 0; j < Res[i].size(); ++j)
			fout << Res[i][j] << " ";
		fout << '\n';
	}
}

int main()
{
	fin >> N >> M;
	for (int i = 1, a, b; i <= M; ++i)
	{
		fin >> a >> b;
		G[a].push_back(b);
		Gt[b].push_back(a);
	}
	Componente_Tare_Conexe();
	fin.close(); fout.close();
	return 0;
}