Cod sursa(job #1335253)

Utilizator andreiulianAndrei andreiulian Data 5 februarie 2015 12:00:37
Problema Componente biconexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include<fstream>
#include<vector>
#include<stack>
#define pb push_back
#define st s.top()
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
int N,M,t[100005],niv[100005],l[100005],u,af[100005];
bool viz[100005];
vector<int> v[100005];
vector< pair<int,int> > sol[200005];
vector< pair<int,int> > :: iterator it;
stack< pair<int,int> > s;
void df(int i);
int main()
{
	in>>N>>M;
	int i,a,b;
	for(i=1;i<=M;++i)
	{
		in>>a>>b;
		v[a].pb(b);
		v[b].pb(a);
	}
	df(1);
	out<<u<<'\n';
	for(i=1;i<=u;++i)
	{
		for(it=sol[i].begin();it!=sol[i].end();++it)
		{
			if(af[it->first]!=i)
			out<<it->first<<' ',af[it->first]=i;
			if(af[it->second]!=i)
			out<<it->second<<' ',af[it->second]=i;
		}
		out<<'\n';
	}
}
void df(int i)
{
	vector<int> :: iterator it;
	viz[i]=1;
	niv[i]=niv[t[i]]+1;
	l[i]=niv[i];
	for(it=v[i].begin();it!=v[i].end();++it)
	if(*it!=t[i])
	{
		if(viz[*it])
			{if(l[i]>l[*it])
			{
				l[i]=l[*it];
				s.push(make_pair(i,*it));
			}}
		else
		{
			t[*it]=i;
			s.push(make_pair(i,*it));
			df(*it);
			l[i]= l[*it]<l[i] ? l[*it] : l[i];
			if(l[*it]>=niv[i])
			{
				++u;
				while(st.first!=i && st.second!=*it)
				{
					//cout<<'('<<st.first<<';'<<st.second<<')'<<' ';
					sol[u].push_back(st);
					s.pop();
				}
				//cout<<'('<<st.first<<';'<<st.second<<')'<<' ';
				sol[u].push_back(st);
				s.pop();
				//cout<<'\n';
			}
		}

	}
}