Cod sursa(job #850776)

Utilizator razvan9310FMI - Razvan Damachi razvan9310 Data 8 ianuarie 2013 22:24:23
Problema Componente tare conexe Scor 94
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <vector>
using namespace std;

vector<int> a[200000], b[200000];
int n, m, v[200000], st[200000], k, nrc;
ofstream out("ctc.out");

void citire()
{
	int i, x, y;
	ifstream in("ctc.in");
	in>>n>>m;
	for (i=0;i<m;++i)
	{
		in>>x>>y;
		a[x].push_back(y);
		b[y].push_back(x);
	}
	in.close();
}

void dfs1(int nod)
{
	v[nod] = 1;
	vector<int>::iterator i = a[nod].begin(), stop = a[nod].end();
	while (i != stop)
	{
		if (!v[*i])
			dfs1(*i);
		++i;
	}
	st[++k] = nod;
}

vector<int> ctc[200000];

void dfs2(int nod)
{
	ctc[nrc].push_back(nod);
	v[nod] = 0;
	--k;
	vector<int>::iterator i = b[nod].begin(), stop = b[nod].end();
	while (i != stop)
	{
		if (v[*i])
			dfs2(*i);
		++i;
	}
}

int main()
{
	citire();
	for (int i=1; i<=n && k<n; ++i)
		if (!v[i])
			dfs1(i);
	while (k)
	{
		++nrc;
		dfs2(st[k]);
	}
	
	out<<nrc<<"\n";
	for (int j=1; j<=nrc; ++j)
	{
		vector<int>::iterator i = ctc[j].begin(), stop = ctc[j].end();
		while (i != stop)
		{
			out<<(*i)<<" ";
			++i;
		}
		out<<"\n";
	}
}