Cod sursa(job #493347)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 17 octombrie 2010 20:40:46
Problema Componente tare conexe Scor 76
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <fstream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>


#define NMAX 100001

using namespace std;

vector<int> C[NMAX],G[NMAX];
stack<int> S;
int V[NMAX];
int N,M;
int K;
bool viz[NMAX];
queue<int> Q;
int NR;
vector<int>CTC[NMAX];

inline void citire()
{
	fstream fin("ctc.in",ios::in);
	fin>>N;
	fin>>M;
	int x,y;
	
	for(int i=1;i<=M;i++)
	{
		fin>>x>>y;
		G[x].push_back(y);
		C[y].push_back(x);
	}
	fin.close();
}

inline void afisare()
{
	fstream fout("ctc.out",ios::out);
		
	fout<<NR<<"\n";
	
	for(int i=1;i<=NR;i++)
	{
		for(unsigned int j=0;j<CTC[i].size();j++)
			fout<<CTC[i][j]<<" ";
		fout<<"\n";
	}
	fout.close();
}


void DFS(int x)
{
	viz[x]=true;
	for(unsigned int i=0;i<G[x].size();i++)
	{
		if(!viz[G[x][i]])
			DFS(G[x][i]);
	}
	V[K--]=x;
}

void DF()
{
	int x;
	while(!S.empty())
	{
		x=S.top();
		viz[x]=true;
		S.pop();
		Q.push(x);
		for(unsigned int i=0;i<C[x].size();i++)
		{
			if(!viz[C[x][i]])
				S.push(C[x][i]);
		}
	}
}



int main(int argc, char*argv[])
{
	citire();
	K=N;
	for(int i=1;i<=N;i++)
		if(!viz[i])
			DFS(i);
	memset(viz,false,sizeof(viz));
	
	for(int i=1;i<=N;i++)
	{
		if(!viz[V[i]])
		{
			S.push(V[i]);
			DF();
			if(Q.size()>0)
				NR++;
			while(!Q.empty())
			{
				CTC[NR].push_back(Q.front());
				Q.pop();
			}
		}
	}
	
	afisare();
}