Cod sursa(job #1699658)

Utilizator Gabiap2015Apostol Gabriel Gabiap2015 Data 8 mai 2016 09:59:25
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
// Biconex.cpp : Defines the entry point for the console application.
//

#include "iostream"
#include "fstream"
#include "vector"
#include "stack"
#include "algorithm"
using namespace std;

int n, m, BicNr;
vector<vector<int>> graf;
vector<int>  eBiconex[10000];
vector<int> nivel, low;
stack<int> muchii_st;

ifstream biconex_in("biconex.in");
ofstream biconex_out("biconex.out");

void pop_st(int nod_start, int nod_end)
{
	while (muchii_st.top() != nod_end)
	{
		eBiconex[BicNr].push_back(muchii_st.top());
		muchii_st.pop();
	}
	muchii_st.pop();
	eBiconex[BicNr].push_back(nod_start);
	eBiconex[BicNr].push_back(nod_end);
}

void dfs(int nod,int k)
{
	nivel[nod] = low[nod] = k;

	for (int i = 0; i < graf[nod].size(); i++)
	{
		int next_nod =  graf[nod][i];
		if (!nivel[next_nod])
		{
			muchii_st.push(next_nod);
			dfs(next_nod, k + 1);

			low[nod] = min(low[nod], low[next_nod]);
			if (low[next_nod] >= nivel[nod])
			{
				BicNr++;
				pop_st(nod, next_nod);
			}
		}
		else
			low[nod] = min(low[nod], nivel[next_nod]);
	}
}
 
int main()
{
	int x, y;
	biconex_in >> n >> m;
	cout << n << ' ' << m << endl;
	nivel.resize(n+1);
	low.resize(n+1);
	graf.resize(n+1);
	for (int i = 1; i <= m; i++)
	{
		biconex_in >> x >> y;
		graf[x].push_back(y);
		graf[y].push_back(x);
	}

	muchii_st.push(1);
	dfs(1, 1);

	biconex_out << BicNr << endl;
	for (int i = 1; i <= BicNr; i++)
	{
		for (int j = 0; j < eBiconex[i].size(); j++)
			biconex_out << eBiconex[i][j] << ' ';
		biconex_out << endl;
	}
	return 0;
}