Cod sursa(job #529162)

Utilizator rares192Preda Rares Mihai rares192 Data 4 februarie 2011 13:56:00
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include<fstream>
#include<vector>
#include<algorithm>
#include<stack>
#include<bitset>
using namespace std;

#define pb push_back
#define p push

ofstream fout("ctc.out");

bool cmp(const int x, const int y)
{
	return x < y;
}

void read();
void DF(int );
void write();
void DFT(int );

vector<vector<int> > a, at;
int n, m, nr = 1, nrc;
bitset<100005> s;
vector<int > sol[100002];
stack<int > S;

int main()
{
	read();
	
	for(int i = 1; i <= n; ++i)
		if( !s[i] )
			DF(i);
		
	while( !S.empty() )
	{
		if( s[ S.top() ] )
		{
			nrc++;
			DFT( S.top() );
			S.pop();
		}
		else
			S.pop();
	}
		
	write();
	return 0;
}

void read()
{
	ifstream fin("ctc.in");
	
	fin >> n >> m;
	a.resize(n+1);
	at.resize(n+1);
	int x, y;
	
	for(int i = 1; i <= m; ++i)
	{
		fin >> x >> y;
		a[x].pb(y);
		at[y].pb(x); // a transpus
	}
	
	fin.close();
}


void DF(int x)
{
	s[x] = 1;
	
	vector<int >::iterator it;
	
	for(it = a[x].begin(); it != a[x].end(); ++it)
		if( !s[*it ] )
			DF( *it );
		
		S.p(x);
}

void DFT(int x)
{
	sol[nrc].pb(x);
	s[x] = 0;
	
	for(vector<int >::iterator it = at[x].begin(); it != at[x].end(); ++it)
		if( s[ *it ] == 1)
			DFT( *it );
}
	


void write()
{
	fout << nrc << '\n';
	
	for(int i = 1; i <= nrc; i++)
	{
	sort(sol[i].begin(), sol[i].end(), cmp);
	
//	int id = sol[i].size();
//	fout << id <<" ";
	
	vector<int >::iterator it, sf = sol[i].end();
	
	for(it = sol[i].begin(); it != sf; ++it)
		fout << *it <<" ";
	
	fout << '\n';
	}
	
}