Cod sursa(job #581020)

Utilizator mottyMatei-Dan Epure motty Data 13 aprilie 2011 18:13:31
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int N = 100001;

int n;
int pos;
int cCount;
int ord[N];

bool vis[N];

vector <int> g[N];
vector <int> r[N];
vector <int> c[N];

void Read()
{
	int m;
	in >> n >> m;

	while (m--)
	{
		int a, b;
		in >> a >> b;

		g[a].push_back(b);
		r[b].push_back(a);
	}
}

void DiggIn(int node)
{
	vis[node] = true;

	for (int i = 0; i < g[node].size(); ++i)
		if (!vis[g[node][i]])
			DiggIn(g[node][i]);

	ord[++pos] = node;
}

void GetOrder()
{
	for (int i = 1; i <= n; ++i)
		if(!vis[i])
			DiggIn(i);
}

void Add(int node, int comp)
{
	vis[node] = false;
	c[comp].push_back(node);

	for (int i = 0; i < r[node].size(); ++i)
		if (vis[r[node][i]])
			Add(r[node][i], comp);
}

void GetComps()
{
	for (int i = 1; i <= n; ++i)
		if (vis[ord[i]])
			Add(ord[i], ++cCount);
}

void PrintComps()
{
	out << cCount << "\n";

	for (int i = 1; i <= cCount; ++i)
	{
		for (int j = 0; j < c[i].size(); ++j)
			out << c[i][j] << " ";

		out << "\n";
	}
}

int main()
{
	Read();

	GetOrder();
	GetComps();
	PrintComps();

	return 0;
}