Cod sursa(job #754127)

Utilizator sunt_emoSunt emo sunt_emo Data 31 mai 2012 19:42:56
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <vector>
#include <list>

using namespace std;

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

int N,M,nr;

vector<vector<int> > G;
vector<vector<int> > rG;
vector<vector<int> > sol;
list<int> ls;

bool mark[100010];

void expand(int u)
{
	if (mark[u])
		return;
	mark[u] = true;
	int sz = (int) G[u].size();
	for (int i = 0; i < sz; i++)
		expand(G[u][i]);
	ls.push_back(u);
}

void expand2(int u)
{
	if(!mark[u])
		return;
	mark[u] = false;
	int sz = (int) rG[u].size();
	for (int i = 0; i < sz; i++)
		expand2(rG[u][i]);
	sol[nr].push_back(u);
}

void init()
{
	for (int i = 0; i <= N; i++)
	{
		G.push_back(vector<int>());
		rG.push_back(vector<int>());
	}
}

int main()
{
	in >> N >> M;

	init();

	for (int i = 0; i < M; i++)
	{
		int x,y;
		in >> x >> y;
		G[x].push_back(y);
		rG[y].push_back(x);
	}

	for (int i = 1; i <= N; i++)
		expand(i);

	while (!ls.empty())
	{
		int u = ls.back();
		ls.pop_back();
		if (mark[u])
		{
			sol.push_back(vector<int>());
			expand2(u);
			nr++;
		}
	}

	out << nr << "\n";
	for (int i = 0; i < nr; i++)
	{
		int sz = (int) sol[i].size();
		for (int j = 0; j < sz; j++)
			out << sol[i][j] << " ";
		out << "\n";
	}

	in.close();
	out.close();
}