Cod sursa(job #631337)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 7 noiembrie 2011 20:20:04
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.3 kb
#include<iostream>
#include<fstream>
#include<string.h>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;


#define NMAX 100050

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

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

int NrComponente;

int N, M;
int S, T;
int NodCautat;

int nivel[NMAX];
int ancestor[NMAX];

void Citire();
void Afisare();
void Preproc();
void DFS(int startNode);


void Citire()
{
	fstream fin(infile, ios::in);
	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 << 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();
}


void Preproc()
{
	memset(nivel, 0xFF, (N+1)<<2);
}

void DFS(int startNode)
{
	ancestor[startNode] = nivel[startNode];
	for(vector<int>::iterator itr = Graph[startNode].begin();
		itr != Graph[startNode].end(); itr++)
	{
		if(nivel[*itr] == -1)
		{
			
			nivel[*itr] = nivel[startNode] +1;
			StivaMuchii.push(make_pair(startNode, *itr));
			DFS(*itr);
			if(ancestor[*itr] >= nivel[startNode])
			{
				
				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++;
			}

			ancestor[startNode] = ancestor[startNode] < ancestor[*itr] ? ancestor[startNode] : ancestor[*itr];
		}
		else
		{
			if(nivel[startNode] > nivel[*itr] +1)
				ancestor[startNode] = ancestor[startNode] < ancestor[*itr] ? ancestor[startNode] : ancestor[*itr];
		}
	}
}




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