Cod sursa(job #1268489)

Utilizator Mr.DoomRaul Ignatus Mr.Doom Data 20 noiembrie 2014 23:37:34
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <vector>
#include <set>
#include <stack>
using namespace std;

ifstream is("biconex.in");
ofstream os("biconex.out");

stack<pair<int, int> > s;
set<int> com[100001];
vector<vector<int> > G;
int L[100001], Niv[100001];
int n, m, k; 

void DF(int x, int t, int nv);
void Extract(int x, int y);

int main()
{
	is >> n >> m;
	int x, y;
	G = vector<vector<int> >(n + 1);
	for ( int i = 1; i <= m; ++i )
	{
		is >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	DF(1, 0, 1);
	os << k << '\n';
	for ( int i = 1; i <= k; ++i )
	{
		for ( set<int>::iterator it = com[i].begin(); it != com[i].end(); ++it )
			os << *it << ' ';
		os << '\n';
	}	
	is.close();
	os.close();
	return 0;
}

void DF(int x, int t, int nv)
{
	L[x] = Niv[x] = nv;
	for ( vector<int>::iterator it = G[x].begin(); it != G[x].end(); ++it )
	{
		if ( *it == t )
			continue;
		if ( !Niv[*it] )
		{
			s.push({x, *it});
			DF(*it, x, nv + 1);
			L[x] = min(L[x], L[*it]);
			if ( L[*it] >= Niv[x] )
			{
				k++;
				Extract(x, *it);
			}
		}
		else
			L[x] = min(L[x], Niv[*it]);
	}
}
void Extract(int x, int y)
{
	int nod, vec;
	do
	{
		nod = s.top().first;
		vec = s.top().second;
		com[k].insert(nod);
		com[k].insert(vec);
		s.pop();
	} while ( nod != x || vec != y );
}