Cod sursa(job #1907498)

Utilizator horiainfoTurcuman Horia horiainfo Data 6 martie 2017 19:33:31
Problema Componente biconexe Scor 42
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

struct Graf { int level, returnLevel; vector<int> v; };

int n, index, nrComp;

Graf node[100002];
vector<int> comp[100002];

stack<int> myStack;

void GoVisit(int nod, int level)
{
	node[nod].level = level;
	node[nod].returnLevel = level;

	myStack.push(nod);

	for (vector<int>::iterator it = node[nod].v.begin(); it != node[nod].v.end(); it++)
		if (!node[*it].level)
		{
			GoVisit(*it, level + 1);
			if (node[*it].returnLevel < level)
				node[nod].returnLevel = min(node[nod].returnLevel, node[*it].returnLevel);
			else
			{
				nrComp++;
				while (myStack.top() != nod)
				{
					comp[nrComp].push_back(myStack.top());
					myStack.pop();
				}
				comp[nrComp].push_back(nod);
			}
		}
		else if (node[*it].returnLevel < node[nod].returnLevel && node[*it].level != level - 1)
			node[nod].returnLevel = node[*it].returnLevel;
}

int main()
{
	int m, n1, n2;

	fin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		fin >> n1 >> n2;
		node[n1].v.push_back(n2);
		node[n2].v.push_back(n1);
	}

	GoVisit(1, 1);

	if (myStack.size() > 1)
	{
		nrComp++;
		while (myStack.size())
		{
			comp[nrComp].push_back(myStack.top());
			myStack.pop();
		}
	}

	fout << nrComp << '\n';
	for (int i = 1; i <= nrComp; i++)
	{
		sort(comp[i].begin(), comp[i].end());
		for (int j = 0; j < comp[i].size(); j++)
			fout << comp[i][j] << ' ';
		fout << '\n';
	}

	return 0;
}