Cod sursa(job #548581)

Utilizator miticaMitica mitica Data 7 martie 2011 16:31:35
Problema Componente biconexe Scor 58
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

const int nmax = 100005;

vector <int> G[nmax],sol[nmax];
vector <int>::iterator it;
stack < pair<int, int> > S;
int n,m,k,i,x,y,u,nv[nmax],L[nmax];

void salveaza(int x, int y)
{
    int p,u;

    k++;
    do{
        p=S.top().first;
        u=S.top().second;
        S.pop();
        sol[k].push_back(p);
        sol[k].push_back(u);
      }while (p!=x || u!=y);
}

void df(int nod, int tata, int adanc)
{
    vector<int>::iterator it;

	nv[nod]=L[nod]=adanc;
	for(it=G[nod].begin();it!=G[nod].end();++it)
	{
        if(*it!=tata)
			if(nv[*it])
				L[nod]=min(L[nod],nv[*it]);
			else
			{
                S.push(make_pair(nod,*it));
				df(*it,nod,adanc+1);
				L[nod]=min(L[nod],L[*it]);
				if(L[*it]>=nv[nod])
					salveaza(nod,*it);
			}
	}
}

int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    scanf("%d %d", &n, &m);
    for (i=1;i<=m;i++)
    {
        scanf("%d %d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    df(1,-1,1);
    printf("%d\n", k);
    for (i=1;i<=k;i++)
    {
        sort(sol[i].begin(), sol[i].end());
        for (it=sol[i].begin();it!=sol[i].end();it++)
            if(*it!=u)
                printf("%d ", (u=*it));
        printf("\n");
    }
    return 0;
}