Cod sursa(job #720493)

Utilizator pitradaPit-Rada Ionel-Vasile pitrada Data 22 martie 2012 18:17:30
Problema Componente biconexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 2.36 kb
#include<stdio.h>
#include<vector>
#include<stack>
#define infile "biconex.in"
#define outfile "biconex.out"
#define nmax 100002

using namespace std;

int n,m,k,hh; //nr noduri/muchii
int xx[200002],pp[200002];
int timp,start,nrfii,nrc,x1,x2;
int nrv[nmax];//numar vecini
int sus[nmax]; // cel mai de sus nod in care poate urca
int d[nmax];//nodul a fost atins la pasul k
struct pereche
{
    int x,y;
};

pereche s[200002],w[200002]; //stiva
vector<int> v[nmax]; //listele de adiacenta

void read()
{
    int i,x,y;
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d %d",&x,&y);
        nrv[x]++;
        nrv[y]++;
        v[x].push_back(y);
        v[y].push_back(x);
    }
}

void df(int nod,int tata)
{
    int i,fiu,x1,x2;
	timp++;
	d[nod]=timp;
	sus[nod]=timp;
	for(i=0;i<nrv[nod];i++)
	{
		fiu=v[nod][i];

		if(!d[fiu])
		{
			k++;
			s[k].x=nod;
			s[k].y=fiu;
			if(nod==start)
				nrfii++;
			df(fiu,nod);
			if(sus[fiu]>=d[nod]) // nodul este punct de articulatie
				if(tata!=-1)
                    {
                        nrc++;
						pp[nrc]=1+hh;//
                        do
                        {
                            x1=s[k].x;
                            x2=s[k].y;
							hh++;
							w[hh]=s[k];
                            k--;
                        }
                        while (x1!=nod || x2!=fiu);
					}
			if(sus[fiu]<sus[nod])
				sus[nod]=sus[fiu];
		}
		else
			if(fiu!=tata)
				if(sus[fiu]<sus[nod])
					sus[nod]=sus[fiu];
	}
}

int main()
{
    freopen(infile,"r",stdin);
    freopen(outfile,"w",stdout);

    read();
    timp=0;
    nrfii=0;
    start=1;
    df(1,-1);
	//printf("***\n%d\n",k);
	//for (int j=k;j>=1;j--)printf("%d %d\n",s[j].x, s[j].y);
	//printf("\n\n");
    while (k>0)
    {
        nrc++;
		pp[nrc]=1+hh;
        do
        {
            x1=s[k].x;
            x2=s[k].y;
			hh++;
			w[hh]=s[k];
            k--;
        }
        while(x1!=1 && x2!=1);
    }
	pp[nrc+1]=1+hh;
    printf("%d\n",nrc);
	for (int k=1;k<=nrc;k++)
	{
		for (int j=pp[k];j<pp[k+1];j++)
		{
			x1=w[j].x;
			x2=w[j].y;
			xx[x1]=1;
			xx[x2]=1;
		}
		for (int j=1;j<=n;j++)
			if (xx[j]!=0)
			{
				printf("%d ",j);
				xx[j]=0;
			}
		printf("\n");
	}
    fclose(stdin);
    fclose(stdout);
    return 0;
}