Cod sursa(job #631224)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 7 noiembrie 2011 14:19:38
Problema Componente biconexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 2.39 kb
#include<iostream>
#include<fstream>


#include<vector>
#include<stack>
using namespace std;


#define NMAX 100000

const char infile[] = "biconex.in";
const char outfile[] = "biconex.out";

stack<pair<int, int> > StivaMuchii;
vector<int> Graph[NMAX];
vector<int> Componente[NMAX];
bool isVizited[NMAX];
int NrComponente;

int N, M;
int S, T;
int NodCautat;
int nivel[NMAX];
int Parinte[NMAX];


void Citire();
void Afisare();
void DFS(int startNode);
void Compute(int startNodeIndex, int endNodeIndex);

void Citire()
{
	fstream fin(infile, ios::in);
	//fin >> S >> T;
	fin >> N >> M;

	int src, dst;
	for(int i = 0 ; i < M; i++)
	{
		fin >> src >> dst;
		Graph[src].push_back(dst);
		Graph[dst].push_back(src);
	}

	fin.close();
}


void Afisare()
{
	fstream fout(outfile, ios::out);

	//fout << "Nodul cautat este = " << NodCautat << "\n";
	fout << NrComponente << "\n";

	
	for(int i = 0 ; i < NrComponente; i++)
	{
		for(vector<int>::reverse_iterator itr = Componente[i].rbegin();
			itr != Componente[i].rend(); itr++)
		{
			fout << *itr << " ";
		}
		fout << "\n";
	}

	fout.close();
}


bool CannotAccessAncestor(int node, int ancestor)
{
	if(nivel[node] >= nivel[ancestor]) 
	{
		return true;
	}
	return false;
	
}

void DFS(int startNode)
{
	isVizited[startNode] = true;
	for(vector<int>::iterator itr = Graph[startNode].begin();
		itr != Graph[startNode].end(); itr++)
	{
		
		if(isVizited[*itr] == true && Parinte[startNode] != *itr)
		{
			nivel[startNode] = nivel[*itr];
		}
		else if(isVizited[*itr] == false)
		{
			Parinte[*itr] = startNode;
			nivel[*itr] = nivel[startNode] +1;

			StivaMuchii.push(make_pair(startNode, *itr));
			DFS(*itr);
			
			if(CannotAccessAncestor(*itr, startNode) == true)
			{
				pair<int, int> edge = make_pair(startNode, *itr);
				
				while(StivaMuchii.top() != edge)
				{
					Componente[NrComponente].push_back(StivaMuchii.top().second);
					StivaMuchii.pop();
					
				}
				Componente[NrComponente].push_back(StivaMuchii.top().second);
				Componente[NrComponente].push_back(StivaMuchii.top().first);
				StivaMuchii.pop();
				NrComponente++;
			}

			if(nivel[startNode] > nivel[*itr])
			{
				nivel[startNode] = nivel[*itr];
			}

		}
		

	}
}




int main(int argc, char* argv[])
{
	Citire();
	for(int i = 0 ; i < N; i++)
		DFS(i);
	Afisare();
}