Cod sursa(job #639932)

Utilizator blk.irineluIrina Ursateanu blk.irinelu Data 24 noiembrie 2011 13:28:28
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <fstream>
#include <vector>
#define maxn 100001
#define maxm 200001

using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");

int n,m,k,poz;
bool viz[maxn];
vector <int> muchii[maxn],sol[maxn];
int lvlmin[maxn],lvl[maxn];
struct muchie
{
    int a,b;
}leg[maxm];

void df(int nod,int tata)
{
    int aux,i;
    viz[nod]=1;
    lvlmin[nod]=lvl[tata]+1;
    lvl[nod]=lvl[tata]+1;
    for(i=0;i<muchii[nod].size();i++)
    {
		aux=muchii[nod][i];
		if(!viz[aux])
		{
			poz++;
			leg[poz].a=nod;
			leg[poz].b=aux;
			df(aux,nod);
			if(lvl[nod]<=lvlmin[aux])
			{
				k++;
				while(leg[poz].a!=nod && leg[poz].b!=aux)
				{
		           sol[k].push_back(leg[poz].b);
		           poz--;
                }
	            sol[k].push_back(leg[poz].b);
	            sol[k].push_back(leg[poz].a);
	            poz--;
			}
			lvlmin[nod]=min(lvlmin[nod],lvlmin[aux]);
			continue;
		}
		else{
			if(aux!=tata)
			 if(lvlmin[nod]>lvl[aux])
				lvlmin[nod]=lvl[aux];
		}
    }
}


int main()
{
    f>>n>>m;
    for(;m;m--)
    {
        int x,y;
        f>>x>>y;
        muchii[x].push_back(y);
        muchii[y].push_back(x);
    }

    for(int i=1;i<=n;i++)
     if(!viz[i]) df(i,1);
    g<<k<<"\n";
    for(int i=1;i<=n;i++)
    {
      for(int j=sol[i].size()-1;j>=0;j--)
        g<<sol[i][j]<<" ";
      g<<"\n";
    }
    return 0;
}