Cod sursa(job #1577960)

Utilizator fromzerotoheroFROM ZERO fromzerotohero Data 24 ianuarie 2016 00:31:21
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>

#define nmax 100001

using namespace std;

ifstream fi("biconex.in");
ofstream fo("biconex.out");

int n, m, a, b, numComp;

int Lev[nmax]; // Lev[i] = Nivelul pe care se afla nodul i in reprezentarea
			   //		   arborescenta a grafului
int Low[nmax]; // Low[i] = Nivelul minim care poate fi atins din nodul i
			   //		   mergand in jos pe arbore si folosind doar muchii
			   //		   de intoarcere pentru intoarcere 
bool viz[nmax];

vector <int> G[nmax], Comp[nmax];
stack < pair <int, int> > S;

void newComp(int tata, int fiu)
{
	int x = S.top().first;
	int y = S.top().second;

	S.pop();

	while (tata != x && fiu != y)
	{
		Comp[numComp].push_back(x);
		Comp[numComp].push_back(y);

		x = S.top().first;
		y = S.top().second;

		S.pop();

	}

	Comp[numComp].push_back(x);
	Comp[numComp].push_back(y);

}

void DFS(int tata)
{
	viz[tata] = true;

	for (int i = 0; i < G[tata].size(); i++)
	{
		int fiu = G[tata][i];

		if (!viz[fiu])
		{
			S.push(make_pair(tata, fiu));

			Lev[fiu] = Low[fiu] = Lev[tata] + 1;
			DFS(fiu);
			Low[tata] = min(Low[tata], Low[fiu]);

			if (Low[fiu] >= Lev[tata])
			{
				numComp++;
				newComp(tata, fiu);
			}
		}
		else
		{
			Low[tata] = min(Low[tata], Lev[fiu]); 
		}

	}

}

void write()
{
	fo << numComp << "\n";
	for (int i = 1; i <= numComp; i++)
	{
		sort(Comp[i].begin(), Comp[i].end());
		Comp[i].push_back(0);
		for (int j = 0; j < Comp[i].size() - 1; j++)
			if (Comp[i][j] != Comp[i][j+1])
				fo << Comp[i][j] << " ";
		fo << "\n";
	}
}

int main()
{

	fi >> n >> m;

	for (int i = 1; i <= m; i++)
	{
		fi >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}

	Lev[1] = Low[1] = 1;

	DFS(1);

	write();

	fi.close();
	fo.close();

	return 0;
}