Cod sursa(job #660347)

Utilizator ELHoriaHoria Cretescu ELHoria Data 12 ianuarie 2012 16:02:10
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <vector>
#include <stack>
#include <bitset>

using namespace std;

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

vector<int> G[100005] ,  aux;
vector< vector<int> > DD;
int N , M , lvl , low[100005] , idx[100005];
bitset<100005> in_stack;
stack<int> st;

void read_data()
{
	int x , y;
	fin>>N>>M;
	for(;M;M--)
	{
		fin>>x>>y;
		G[x].push_back(y);
	}
}

void comp(const int nod)
{
	int v; aux.clear();
	do { aux.push_back(v = st.top());
		st.pop();in_stack[v] = 0;
	}while(v != nod);
	DD.push_back(aux);
}


void df(const int node)
{
	low[node] = idx[node] = ++lvl;
	st.push(node); in_stack[node] =  1;
	for(vector<int>::iterator w = G[node].begin();w!=G[node].end();++w) 
		if(idx[*w] == 0) 
			df(*w) , low[node] = min(low[node],low[*w]);
		else
		if(in_stack[*w] == 1) low[node] = min(low[node],low[*w]);

	if(low[node] == idx[node]) 
		comp(node);
}

void print()
{
	fout<<DD.size()<<'\n';
	for(int i = 0;i <(int) DD.size();++i) {
		for(int j = 0;j <(int) DD[i].size();++j)
			fout<<DD[i][j]<<' ';
	fout<<'\n';
	}
}

int main()
{
	read_data();
	for(int i = 1;i<=N;++i)
		if(idx[i] == 0) df(i); 

	print();
	return 0;
}