Cod sursa(job #449454)

Utilizator Andreid91Ciocan Andrei Andreid91 Data 6 mai 2010 12:52:08
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 5.25 kb
#include<fstream.h>
#include<algorithm>
#include<iostream.h>
#include<vector>

using namespace std;

#define inf 2000000000 


inline int cmp (int x, int y ) { return x<y;} 

ofstream g("misiune.out");

int  p,m,n,k,D,S,niv[100005],low[100005],critic[100005],sw[100005],tt[100005],C;

int sol,q,sw2[100005],st1[100005],st2[100005],nrcb;

vector <int> v[100005];

vector<int> cb[100005];


/*int compara (int x1, int x2 , int val )
{
	if (timp[x1][0]==inf)
		return 1;
	
	int t=0,i;
	for (i=1;i<=timp[x2][0] || t>0; i++)
	{
		w[i]=timp[x2][i]*val+t;
		t=w[i]/10;
		w[i]=w[i]-t*10;
	}
	w[0]=i-1;
	
	if (w[0]<timp[x1][0])
		return 1;
	else
		if (w[0]>timp[x1][0])
			return -1;
	
	for (i=w[0];i>0;--i)
		if (w[i]>timp[x1][i])
			return -1;
		else
			if (w[i]<timp[x1][i])
				return 1;
	return 0;
}*/

/*void inmultire (int x1, int x2, int val )
{
	int t=0,i;
	
	
	if (timp[x1][0]!=inf)
		for (i=1;i<=timp[x1][0];i++)
			timp[x1][i]=0;
	
	for (i=1;i<=timp[x2][0] || t>0; i++)
	{
		timp[x1][i]=timp[x2][i]*val+t%10;
		t=timp[x1][i]/10;
		timp[x1][i]-=t*10;
	}
	
	timp[x1][0]=i-1;
}

void urca (int q)
{
	while (q>1 && timp[h[q]]<timp[h[q/2]] )
	{
		poz[h[q]]=q/2;
		poz[h[q/2]]=q;
		h[q]=(h[q/2]^h[q])^(h[q/2]=h[q]);
		q>>=1;
	}
}

void coboara ()
{
	int x=p,y=1;
	while (x!=y)
	{
		x=y;
		if ((2*x<=p) && (timp[h[2*x]]<timp[h[x]])) y=2*x;
		if (2*x+1<=p && (timp[h[2*x+1]]<timp[h[y]])) y=2*x+1;
		
		poz[h[x]]=y;
		poz[h[y]]=x;
		
		h[x]=(h[x]^h[y])^(h[y]=h[x]);
	}
}

int verif (int max)
{
	int i,j;
	vector <graf> :: iterator it;
	p=1;
	
	for (i=1;i<=n;i++)
			timp[i]=inf;
		
	
	
	memset(poz,0,sizeof(poz));
	memset(best,0,sizeof(best));
	timp[S]=1;
	poz[S]=1;
	h[1]=S;
	
	while (p>=1)
	{
		
		for (it=v[h[1]].begin();it<v[h[1]].end();++it)
			if (timp[it->nod]>timp[h[1]]*(it->t) && best[h[1]]+it->cost <=max ||  timp[it->nod]==timp[h[1]]*(it->t) && best[h[1]]+it->cost < best[it->nod] && best[h[1]]+it->cost<=max)
			
			if (poz[it->nod]==0)
			{
				tt[it->nod]=h[1];
				poz[it->nod]=++p;
				h[p]=it->nod;
				best[it->nod]=best[h[1]]+it->cost;
				if (critic[it->nod])
					best[it->nod]=0;
				timp[it->nod]=timp[h[1]]*(it->t);
				urca (p);
			}
			else
			{
				tt[it->nod]=h[1];
				best[it->nod]=best[h[1]]+it->cost;
				if (critic[it->nod])
					best[it->nod]=0;
				timp[it->nod]=timp[h[1]]*(it->t);
				urca (poz[it->nod]);
			}
				
		h[1]=h[p--];
		coboara();
	}
	
	if (timp[D]==sol)		
	return 1;
	return 0;
}			
void solve ()
{
	int p,s=0,i;
	sort (cap+1,cap+k+1,cmp);
	verif(cap[k]);
	sol=timp[D];
	
	for (p=1;p<=k;p<<=1);
	p>>=1;
	for(;p;p>>=1)
		if (s+p<=k && verif(cap[s+p])==0)
			s+=p;
	C=cap[++s];
}*/
int df (int i)
{
	vector <int> :: iterator it;
	sw[i]=1;
	low[i]=niv[i];
	
	for (it=v[i].begin();it<v[i].end();++it)
		if (sw[*it]==0)
		{
			niv[*it]=niv[i]+1;
			tt[*it]=i;
			st1[++q]=i;
			st2[q]=*it;
			
			df(*it);
			if (low[*it]>=niv[i])
			{
				critic[i]=1;
				nrcb++;
				while (st1[q]!=i || st2[q]!=*it)
				{
					if (sw2[st1[q]]!=nrcb)
					{
						cb[nrcb].push_back(st1[q]);
						sw2[st1[q]]=nrcb;
					}
					if (sw2[st2[q]]!=nrcb)
					{
						cb[nrcb].push_back(st2[q]);
						sw2[st2[q]]=nrcb;
					}
					q--;
				}
				if (sw2[st1[q]]!=nrcb)
					{
						cb[nrcb].push_back(st1[q]);
						sw2[st1[q]]=nrcb;
					}
				if (sw2[st2[q]]!=nrcb)
					{
						cb[nrcb].push_back(st2[q]);
						sw2[st2[q]]=nrcb;
					}
				q--; 
			}					
					
			if (low[*it]<low[i])
				low[i]=low[*it];
		}
		else
			if (*it!=tt[i] && niv[*it]<low[i])
			{
				st1[++q]=i;
				st2[q]=*it;
				low[i]=niv[*it];
			}
			
}

/*void cst()
{
	int i;
	vector <int> :: iterator it,it3;

	for (i=1;i<=nrcb;i++)
		for (it=cb[i].begin();it<cb[i].end();++it)
			root[*it].push_back(i);
	
	for (i=1;i<=nrcb;i++)
		for (it=cb[i].begin();it<cb[i].end();++it)
			for (it3=root[*it].begin();it3<root[*it].end();++it3)
				if ((*it3!=i) && (sw[*it3]!=i))
					{
						a[i].push_back(*it3);
						sw[*it3]=i;
					}
}
*/
/*void deep (int i )
{
	vector <int > :: iterator it;
	sw[i]=1;
	
	for (it=a[i].begin();it<a[i].end();++it)
		if (sw[*it]==0)
		{
			tt[*it]=i;
			deep(*it);
		}
}*/
void nodcritic ()
{
	vector <int> :: iterator it;
	int i,r;
	niv[1]=1;
	df(1);
	critic[1]=0;
	for (i=1;i<=n;i++)
		if (tt[i]==1)
			critic[1]++;
	if (critic[1]>1)
		critic[1]=1;
	else
		critic[1]=0;
	/*
	memset(sw,0,sizeof(sw));
	memset(tt,0,sizeof(tt));
	memset(sw2,0,sizeof(sw2));
	cst();
	memset(sw,0,sizeof(sw));
	
	deep(root[S][0]);
	memset(sw,0,sizeof(sw));
	
	for (it=root[S].begin();it<root[S].end();++it)
		sw2[*it]=1;
	for (it=root[D].begin();it<root[D].end();++it)
		sw2[*it]=1;
	
		
	r=root[D][0];
	while (r!=root[S][0])
	{
		sw2[r]=1;
		r=tt[r];
	}
	for (i=1;i<=nrcb;++i)
		if (sw2[i]==1)
			for (it=cb[i].begin();it<cb[i].end();++it)
				sw[*it]=1; */
}
/*void drum (int i )
{
	if (S==i)
		g<<S<<' ';
	else
	{
		drum(tt[i]);
		g<<i<<' ';
	}
}*/

void afisare ()
{
	int i,x,nr;
	vector <int> :: iterator it;
	ofstream g("misiune.out");
	g<<nrcb<<'\n';
	for (i=1;i<=nrcb;++i)
	{
		for (it=cb[i].begin();it<cb[i].end();++it)
			g<<*it<<' ';
		g<<'\n';
	}
	g.close();
}

void citire ()
{
	int i,x,y;
	ifstream f("misiune.in");
	f>>n>>m;//>>k>>S>>D;
	
//	for (i=1;i<=k;i++)
	//	f>>cap[i];
	
	for (i=1;i<=m;i++)
	{
		f>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	f.close();
}

int main()
{
	citire ();
	nodcritic ();
	//solve ();
	afisare ();
	return 0;
}