Cod sursa(job #1293064)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 15 decembrie 2014 11:49:42
Problema Componente biconexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <cstdio>
#include <vector>
#define Nmax 200005

using namespace std;

int n,niv[Nmax],low[Nmax],nrcomp,st[Nmax],top;
bool viz[Nmax];
vector <int> L[Nmax],Sol[Nmax];

inline void Dfs(int nod, int cnt)
{
    niv[nod]=cnt; viz[nod]=true;
    vector <int>::iterator it;
    for(it=L[nod].begin();it!=L[nod].end();++it)
        if(viz[*it])
            low[nod]=niv[*it];
        else
        {
            Dfs(*it,cnt+1);
            low[nod]=min(low[nod],low[*it]);
        }
}

inline void Dfs1(int nod)
{
    viz[nod]=true; st[++top]=nod;
    vector <int>::iterator it;
    for(it=L[nod].begin();it!=L[nod].end();++it)
        if(!viz[*it])
        {
            Dfs1(*it);
            if(low[*it]>=niv[nod])
            {
                ++nrcomp;
                for(;top && st[top]!=*it;--top) Sol[nrcomp].push_back(st[top]);
                Sol[nrcomp].push_back(st[top--]);
                Sol[nrcomp].push_back(nod);
            }
        }
}

int main()
{
    int m,x,y,i;
    vector <int>::iterator it;
    freopen ("biconex.in","r",stdin);
    freopen ("biconex.out","w",stdout);
    scanf("%d%d", &n,&m);
    while(m--)
    {
        scanf("%d%d", &x,&y);
        L[x].push_back(y);
        L[y].push_back(x);
    }
    Dfs(1,0);
    for(i=1;i<=n;++i) viz[i]=false;
    Dfs1(1);
    printf("%d\n", nrcomp);
    for(i=1;i<=nrcomp;++i)
    {
        for(it=Sol[i].begin();it!=Sol[i].end();++it) printf("%d ", *it);
        printf("\n");
    }
    return 0;
}