Cod sursa(job #654231)

Utilizator batistaUPB-Oprea-Cosmin-Dumitru batista Data 29 decembrie 2011 21:34:46
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include<fstream>
#define inf 32766
using namespace std;
int i,j,x,y,n,st,nivmin[100002],critic[100002],niv[100002],nrfiirad,fiu[3],q,q2,m;
struct nod{short info;nod*adr;}*v[100002],*p;
char viz[100002],viz2[1002];
ofstream g("kgb.out");
void dfs_biconex(int tata,int nd,int nv,int maxx)
{
	viz[nd]='1';
	nivmin[nd]=nv;
	if(tata==1) nrfiirad++;
	nod *p=v[nd];
	niv[nd]=nv;
	while(p)
	{
		if(!viz[p->info]) 
	    {
		  dfs_biconex(nd,p->info,nv+1,1);
		  if(nivmin[p->info]>maxx )maxx=nivmin[p->info];
		}
		else
		{
		  if( nivmin[p->info] < nivmin[nd] ) nivmin[nd]=nivmin[p->info];
			  p=p->adr;
		}
	}
	if(maxx<niv[nd]) {critic[nd]=1;q++; }
}
void afisare()//verific si nodul 0
{int nr=0,nod,c[1002]={0},ok=1;
	for(i=1;i<=n;i++)
		if(critic[i]==0){ nr++; c[nr]=i; }
	/*if(nr==1) g<<"KGB este forte";
		else*/
		{
			/*g<<"KGB nu este forte\n";
			for(i=1;i<=nr;i++) g<<c[i]<<" ";*/
			g<<nr+1<<"\n";
				
		}
}
int main()
{
	ifstream f("biconex.in");ofstream g("biconex.out");//caz special pt radacina
	f>>n>>m;
	for(i=1;i<=n;i++)nivmin[i]=inf;
	while(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;
	}
	for(i=1;i<=n;i++)
		if(!viz[i]) dfs_biconex(-1,i,1,1);
	critic[1]=1;//critic[x]=1 <=> x nu e critic
	if(nrfiirad>1)critic[1]=0;
	afisare();
return 0;}