Cod sursa(job #917179)

Utilizator zig_zagFMI Alexandru Gabriel zig_zag Data 17 martie 2013 13:52:26
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

ifstream in("biconex.in"); ofstream out("biconex.out");
int n,m,nr=0;

vector <int> v[100001], low, lvl, v2[50001];
stack < pair <int,int> > s;
pair <int, int> l;

void read()
{
	int a,b;
	in >> n >> m;
	low.resize(n+2);
	lvl.resize(n+2);
	for (int i=1; i<=m; i++)
	{
		in >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	for (int i=0; i<=n; i++)
		lvl[i]=0;
}

int min(int a, int b)
{
	if (a<b)
		return a;
	else
		return b;
}

void dfs(int x, int px, int k)
{
	int y;
	lvl[x]=low[x]=k;
	for (int i=0; i<v[x].size(); i++)
	{
		y=v[x][i]; 
		if(y!=px)
		{
			if (lvl[y])
				low[x]=min(low[x],lvl[y]);
			else			
			{
				s.push(make_pair(x,y));
				dfs(y,x,k+1);
				low[x]=min(low[x],low[y]);
				if (low[y]>=lvl[x])
				{
					nr++;
					do 
					{
						l=s.top();
						s.pop();
						v2[nr].push_back(l.second);
					} while (l!=make_pair(x,y));
					v2[nr].push_back(l.first);
				}
			}
		}		
	}
}

void write()
{
	out << nr << "\n";
	for (int i=1; i<=nr; i++)
	{
		for (int j=0; j<v2[i].size(); j++)
			out << v2[i][j] << " ";
		out << "\n";
	}
}

int main ()
{
	read();
	dfs(1,1,1);
	write();
}