Cod sursa(job #527080)

Utilizator dornescuvladVlad Eugen Dornescu dornescuvlad Data 30 ianuarie 2011 16:27:50
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
/* Kosaraju's Algorithm */

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const char iname[] = "ctc.in";
const char oname[] = "ctc.out";
const int  nmax    =  100001;

ifstream fin(iname);
ofstream fout(oname);

int n, m, x, y, i, j, nrc, nrnod;
vector<int> Gr[nmax];
vector<int> Gt[nmax];
int viz[nmax], viz2[nmax], luat[nmax];
int C[200][nmax];
int v[nmax], k, v2[nmax];

void DF(int nod)
{	
	v[++k] = nod;
	viz[nod] = 1;
	for(vector<int>::iterator it = Gr[nod].begin(); it != Gr[nod].end(); ++ it)
	{
		if(viz[*it] == 0)
			DF(*it);
	}
	
}

void DF2(int nod)
{	
	luat[nod] = nrc;
	C[nrc][++C[nrc][0]] = nod;
	nrnod--;
	viz2[nod] = 1;
	int k2 = 0;
	for(vector<int>::iterator it = Gt[nod].begin(); it != Gt[nod].end(); ++ it)
		if(viz2[*it] == 0)
			DF2(*it);
	
}
	
int main()
{
	fin >> n >> m;
	for(i = 1; i <= m; i ++)
	{
		fin >> x >> y;
		Gr[x].push_back(y);
		Gt[y].push_back(x);
	}
	
	DF(1);
	nrnod = n;
	while(nrnod > 0)
	{
		for(j = 1; j <= k; j ++)
			{	
				if(viz2[v[j]] == 0)
				{	
					nrc++;
					DF2(v[j]);
				}
			}
		for(i = 1; i <= n; i ++)
		    if(!luat[i])
		    {
			nrnod --;
			C[++nrc][0] = 1;
			C[nrc][1] = i;
		    }
	}
	fout << nrc << "\n";
	for(i = 1; i <= nrc; i ++)
	{
		for(j = 1; j <= C[i][0]; j ++)
			fout << C[i][j] << " ";
		fout << "\n";
	}
	return 0;
}