Cod sursa(job #765428)

Utilizator danalex97Dan H Alexandru danalex97 Data 7 iulie 2012 16:55:33
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <vector>
using namespace std;

ifstream F("ctc.in");
ofstream G("ctc.out");

#define Nmax 100011
#define Mmax 200011

vector<int> First[Nmax],Second[Nmax];
vector<int> Sol[Nmax];
int Stiva[Nmax],Size;
int Used[Nmax],Mark[Nmax];
int N,M,Co;

void DFF(int Nod)
{
	Used[Nod]=1;
	int Stop=First[Nod].size();
	
	for (int i=0;i<Stop;++i)
		if ( !Used[First[Nod][i]] )
			DFF( First[Nod][i] );
	
	Stiva[++Size]=Nod;
}

void DFS(int Nod, int Value) 
{
    Mark[Nod] = Value;
	int Stop=Second[Nod].size();
	
    for (int i = 0; i < Stop; ++i) 
		if ( Mark[ Second[Nod][i]] == 0 )
            DFS( Second[Nod][i], Value);    
}

int main()
{
	F>>N>>M;
	for (int i=1;i<=M;++i)
	{
		int x,y;
		F>>x>>y;
		First[x].push_back(y);
		Second[y].push_back(x);
	}
	
	for (int i=1;i<=N;++i)
		if ( !Used[i] )
			DFF(i);
	for ( ;Size; Stiva[Size--]=0 )
		if ( Mark[ Stiva[Size] ] == 0 )
			DFS(Stiva[Size],++Co);
	
	for (int i=1;i<=N;++i)
        Sol[Mark[i]].push_back(i);
	
	G<<Co<<"\n";
    for (int i=1;i<=Co;++i) 
	{
        for (unsigned int j=0;j<Sol[i].size();++j)
            G<<Sol[i][j]<<" ";
        G<<"\n";
    }
}