Cod sursa(job #938003)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 11 aprilie 2013 16:18:08
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#include <bitset>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
using namespace std;

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

const int dim = 100005;
int N, M, NC, top[dim];
vector <int> V[dim], VT[dim], C[dim];
bitset <dim> viz;

void cit ()
{
	fi >> N >> M;
	for (int i = 1, a, b; i <= M; i++)
	{
		fi >> a >> b;
		V[a].push_back (b);
		VT[b].push_back (a);
	}
}

void dfs (int n)
{
	viz[n] = 1;
	for (int i = 0; i < V[n].size(); i++)
		if (viz[V[n][i]] == 0)
			dfs (V[n][i]);
	top[++top[0]] = n;
}

void dfst (int n)
{
	viz[n] = 0;
	C[NC].push_back (n);
	for (int i = 0; i < VT[n].size(); i++)
		if (viz[VT[n][i]])
			dfst (VT[n][i]);
}

void rez ()
{
	for (int i = 1; i <= N; i++)
		if (viz[i] == 0)
			dfs (i);
	for (int i = N; i >= 1; i--)
		if (viz[top[i]])
		{
			NC ++;
			dfst (top[i]);
		}
}

void afi ()
{
	fo << NC << '\n';
	for (int i = 1, j; i <= NC; i++)
	{
		for (j = 0; j < C[i].size(); j++)
			fo << C[i][j] << ' ';
		fo << '\n';
	}
}

int main ()
{
	cit ();
	rez ();
	afi ();
	
	return 0;
}