Cod sursa(job #696209)

Utilizator batistaUPB-Oprea-Cosmin-Dumitru batista Data 28 februarie 2012 17:35:26
Problema Componente biconexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include<fstream>
#define min(a,b) (a<b)?a:b
#define max(a,b) (a>b)?a:b
using namespace std;
int n,m,x,y,i,nr;
int niv[100002],nivmin[100002],st[100002][2],q,nrfii,start=1;
struct nod{int info;nod*adr;}*v[100002],*p;
short viz[100002],critic[100002];
ofstream g("biconex.out");
void afisare(int q)
{
	int i;
	g<<st[1][0]<<" ";
	for(i=1;i<=q;i++)
	 if(st[i][0]==0)
	 {
	   i++;
	   g<<'\n';
	   g<<st[i][1]<<" ";
	 }
	 else
	g<<st[q][1]<<" ";
}
void dfs(int t,int nd,int nv)
{
	viz[nd]=1;
	niv[nd]=nivmin[nd]=nv;
	nod*p=v[nd];
	while(p)
	{
		//if(p->info!=t && niv[p->info]<niv[nd]) { st[++q][0]=p->info; st[q][1]=nd; }
		
		if(!viz[p->info])
		{
		  if(nd==start)nrfii++;
		 dfs(nd,p->info,nv+1);
		 nivmin[nd]=min(nivmin[nd],nivmin[p->info]);
		 if(nivmin[p->info]>=niv[nd])
		 {
			if(nd!=start)critic[nd]=1;
			nr++;
		 }
		}
		else
		if(p->info!=t)
		 nivmin[nd]=min(nivmin[nd],niv[p->info]);
		p=p->adr;
	}
}

int main()
{
	ifstream f("biconex.in");
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
		f>>x>>y;
		p=new nod;
		p->info=y; p->adr=v[x]; v[x]=p;
		p=new nod;
		p->info=x; p->adr=v[y]; v[y]=p;
	}
	dfs(-1,1,1);
	if(nrfii>1)critic[1]=1;
	g<<nr<<"\n";
	afisare(q);
	f.close();g.close();
return 0;}