Cod sursa(job #1208391)

Utilizator pulseOvidiu Giorgi pulse Data 15 iulie 2014 16:18:24
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <vector>
#include <stack>
#define Nmax 100005

using namespace std;

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

int n, m, cnt;
vector <int> G[Nmax], G_T[Nmax], sol[Nmax];
stack <int> st;
bool used[Nmax];

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

void DFS_T(int node)
{
	sol[cnt].push_back(node);
	used[node] = true;
	for (vector <int> :: iterator it = G_T[node].begin(); it != G_T[node].end(); ++it)
	{
		if (!used[*it])
			DFS_T(*it);
	}
}

int main()
{
	fin >> n >> m;
	for (int i = 1; i <= m; ++i)
	{
		int a, b;
		fin >> a >> b;
		G[a].push_back(b);
		G_T[b].push_back(a);
	}

	for (int i = 1; i <= n; ++i)
		if (!used[i])
			DFS(i);

	for (int i = 1; i <= n; ++i)
		used[i] = false;

	while (!st.empty())
	{
		if (!used[st.top()])
		{
			++cnt;
			DFS_T(st.top());
		}
		st.pop();
	}

	fout << cnt << '\n';
	for (int i = 1; i <= cnt; ++i)
	{
		for (vector <int> :: iterator it = sol[i].begin(); it != sol[i].end(); ++it)
			fout << *it << " ";
		fout << '\n';
	}

	fin.close();
	fout.close();
	return 0;
}