Cod sursa(job #1168765)

Utilizator Kira96Denis Mita Kira96 Data 9 aprilie 2014 15:21:34
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include<fstream>
#define N 100100
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector<int> b[N],v[N];
stack<pair<int,int> > st;
int i,n,m,x,y,cb,low[N],niv[N],t,j;
void dfs(int nod,int pr)
{
	++t;
	low[nod]=niv[nod]=t;
	for(int i=0;i<v[nod].size();++i)
		if(v[nod][i]!=pr)
		{
			if(!niv[v[nod][i]])
			{
				st.push(make_pair(nod,v[nod][i]));
				dfs(v[nod][i],nod);
				if(low[v[nod][i]]>=niv[nod])
				{
					int x,y;
					++cb;
					do
					{
						x=st.top().first;
						y=st.top().second;
						b[cb].push_back(y);
						st.pop();
					}
					while(x!=nod&&y!=v[nod][i]);
					b[cb].push_back(nod);
				}
				low[nod]=min(low[nod],low[v[nod][i]]);
			}
			low[nod]=min(low[nod],niv[v[nod][i]]);
		}
	--t;
}
int main ()
{
	f>>n>>m;
	for(i=1;i<=m;++i)
	{
		f>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1,-1);
	g<<cb<<"\n";
	for(i=1;i<=cb;++i)
	{
		for(j=0;j<b[i].size();++j)
			g<<b[i][j]<<" ";
		g<<"\n";
	}
	return 0;
}