Cod sursa(job #412421)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 5 martie 2010 16:57:35
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <stdio.h>
#include <vector>

using namespace std;

const int Lg = 200010;

vector <int> Rez[Lg],Graf[Lg];
int low[Lg],niv[Lg],viz[Lg],st[Lg];
int n,m,nr,nr_rez,vf,a,b;

void citire()
{
    scanf ("%d %d",&n,&m);
    for (int i=0;i<m;i++)
    {
        scanf ("%d %d",&a,&b);
        Graf[a].push_back(b);
        Graf[b].push_back(a);
    }
}

inline int min(int a,int b)
{
    return a<b?a:b;
}

void add(int a,int b)
{
    nr_rez++;
    do
    {
        Rez[nr_rez].push_back(st[--vf]);
        Rez[nr_rez].push_back(st[--vf]);
    }while (st[vf+1]!=b || st[vf]!=a);
}

void df(int nod)
{
    viz[nod]=1;
    low[nod]=niv[nod]=nr++;
    for (int i=0 ; i<Graf[nod].size() ; i++)
        if (!viz[Graf[nod][i]])
        {
            st[vf++]=nod;
            st[vf++]=Graf[nod][i];
            df(Graf[nod][i]);
            if (low[Graf[nod][i]]>=niv[nod])
                add(nod,Graf[nod][i]);
            low[nod]=min(low[nod],low[Graf[nod][i]]);
        }
        else
            low[nod]=min(low[nod],niv[Graf[nod][i]]);
}

void solve()
{
    for (int i=1;i<=n;i++)
        if (!viz[i])
            df(i);
    printf("%d\n",nr_rez);
    for (int i=1;i<=nr_rez;i++)
    {
        for (int j=0;j<Rez[i].size();j++)
            viz[Rez[i][j]]=0;
        for (int j=0;j<Rez[i].size();j++)
            if (!viz[Rez[i][j]])
            {
                viz[Rez[i][j]]=1;
                printf("%d ",Rez[i][j]);
            }
        printf("\n");
    }
}

int main ()
{
    freopen ("biconex.in","r",stdin);
    freopen ("biconex.out","w",stdout);
    citire();
    solve();
    return 0;
}