Cod sursa(job #395836)

Utilizator RobybrasovRobert Hangu Robybrasov Data 13 februarie 2010 20:38:53
Problema Componente biconexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 2.4 kb
#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
#include <algorithm>
#define N 100005
#define inf 0x3f3f3f3f

using namespace std;

vector<int> L[N],rez[N];
stack< pair<int, int> > S;
int jos[N],niv[N],tata[N];
int kont;
char E[N];

void dfs(int nod)
{
    E[nod]=1;
    int min=niv[nod];
    for (vector<int>::iterator it=L[nod].begin(); it!=L[nod].end(); it++)
    {
        //daca e legat cu o muchie inversa de un predecesor diferit de tatal lui
        if (E[*it] && tata[nod]!=*it && niv[*it]<min) min=niv[*it];

        //daca nodul urmator nu a fost descoperit inca
        if (!E[*it])
        {
            tata[*it]=nod; //devine tatal lui
            niv[*it]=niv[nod]+1; //se incrementeaza nivelul
            dfs(*it); //il analizeaza recursiv
            if (jos[*it]<min) min=jos[*it]; //minimul dintre nivelurile minime accesibile
        }
    }
    jos[nod]=min;
}

void biconex(int nod)
{
    E[nod]=1;
    for (vector<int>::iterator it=L[nod].begin(); it!=L[nod].end(); it++)
    {
        //daca e pe muchia de intoarcere
        if (E[*it] && tata[nod]!=*it && niv[*it]<niv[nod])
            S.push(make_pair(nod,*it));

        //daca se afla pe un nod nou
        if (!E[*it])
        {
            S.push(make_pair(nod,*it));
            int nr=*it;
            biconex(nr);
            if (jos[*it]>=niv[nod])
            {
                kont++;
                for (; S.top().first!=nod && S.top().second!=*it; S.pop())
                {
                    rez[kont].push_back(S.top().first);
                    rez[kont].push_back(S.top().second);
                }
                rez[kont].push_back(S.top().first);
                rez[kont].push_back(S.top().second);
                S.pop();
            }
        }
    }
}

int main()
{
    int n,m;
	freopen("biconex.in","r",stdin);
	freopen("biconex.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1; i<=m; i++)
	{
	    int x,y;
	    scanf("%d%d",&x,&y);
	    L[x].push_back(y);
	    L[y].push_back(x);
	}
	memset(E,0,sizeof(E));
	memset(jos,inf,sizeof(jos));
	jos[1]=1;
	niv[1]=1;
	dfs(1);
	memset(E,0,sizeof(E));
	biconex(1);

	printf("%d\n",kont);
	for (int i=1; i<=kont; i++, printf("\n"))
	{
	    sort(rez[i].begin(),rez[i].end());
	    vector<int>::iterator it;
        for (it=rez[i].begin(); it+1!=rez[i].end(); it++)
            if (*it!=*(it+1)) printf("%d ",*(it));
        if (*it!=*(it+1)) printf("%d",*it);
	}

    return 0;
}