Cod sursa(job #1169004)

Utilizator BionicMushroomFMI - Dumitrescu Tiberiu Alexandru BionicMushroom Data 10 aprilie 2014 05:05:32
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include<fstream>
#include<vector>
#include<stack>
using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");
int nr_noduri, nr_muchii;
vector<int> *v;
vector<vector<int>> componenta;
stack<int> s;
int *adancime, *lowpoint;

void DFS(int nod, int distanta)
{
	int fii = 0;
	lowpoint[nod] = adancime[nod] = distanta;
	for (int i = 0; i < v[nod].size(); i++)
		if (!adancime[v[nod][i]])
		{
			s.push(v[nod][i]);
			fii++;
			DFS(v[nod][i], distanta + 1);
			if (lowpoint[v[nod][i]] < lowpoint[nod])
				lowpoint[nod] = lowpoint[v[nod][i]];
			if (lowpoint[v[nod][i]] >= adancime[nod])
			{
				componenta.emplace_back();
				while (s.top() != v[nod][i])
				{
					componenta[componenta.size() - 1].push_back(s.top());
					s.pop();
				}
				s.pop();
				componenta[componenta.size() - 1].push_back(nod);
				componenta[componenta.size() - 1].push_back(v[nod][i]);
			}
		}
		else
			if (adancime[v[nod][i]] < lowpoint[nod] && adancime[nod] - 1 != adancime[v[nod][i]])
				lowpoint[nod] = adancime[v[nod][i]];
}

int main()
{
	f >> nr_noduri >> nr_muchii;
	v = new vector<int>[nr_noduri];
	adancime = new int[nr_noduri];
	lowpoint = new int[nr_noduri];
	for (int i = 0; i < nr_noduri; i++)
		adancime[i] = 0;
	for (int i = 0; i < nr_muchii; i++)
	{
		int nod1, nod2;
		f >> nod1 >> nod2;
		v[nod1 - 1].push_back(nod2 - 1);
		v[nod2 - 1].push_back(nod1 - 1);
	}
	DFS(0, 1);
	g << componenta.size() << endl;
	for (int i = 0; i < componenta.size(); i++)
	{
		for (int j = 0; j < componenta[i].size(); j++)
			g << componenta[i][j] + 1 << ' ';
		g << endl;
	}
	f.close();
	g.close();
	delete[] v;
	delete[] adancime;
	delete[] lowpoint;
	return 0;
}