Cod sursa(job #2285301)

Utilizator savulescustefanSavulescu Stefan savulescustefan Data 18 noiembrie 2018 14:06:08
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
vector <int> s,c[100004],v[100004];
int n,m,i,j,k,x,y,nr,poz,d[100004],l[100004],t[100004];
bool sel[100004];
void g (int x)
{
    int i,k;
    sel[x]=true;
    k=v[x].size()-1;
    d[x]=l[x];
    for (i=0;i<=k;i++)
    {
        if (sel[v[x][i]]==false)
        {
            l[v[x][i]]=l[x]+1;
            t[v[x][i]]=x;
            g(v[x][i]);
        }
        else
        {
            if (l[v[x][i]]<d[x])
                d[x]=l[v[x][i]];
        }
    }
    for (i=0;i<=k;i++)
    {
        if (l[x]<l[v[x][i]])
        {
            if (d[x]>d[v[x][i]])
                d[x]=d[v[x][i]];
        }
    }
    return;
}
void r (int x)
{
    nr++;
    poz=s.size()-1;
    while (s[poz]!=x)
    {
        c[nr].push_back(s[poz]);
        s.pop_back();
        poz--;
    }
    c[nr].push_back(s[poz]);
    c[nr].push_back(t[s[poz]]);
    s.pop_back();
    return;
}
void p (int x)
{
    int i,k,Max;
    k=v[x].size()-1;
    sel[x]=true;
    Max=0;
    for (i=0;i<=k;i++)
    {
        if (sel[v[x][i]]==false)
        {
            s.push_back(v[x][i]);
            p(v[x][i]);
            if (l[x]<=d[v[x][i]])
                r(v[x][i]);
        }
    }
}
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);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    l[1]=1;
    g(1);
    for (i=1;i<=n;i++)
        sel[i]=false;
    nr=0;
    p(1);
    printf ("%d\n", nr);
    for (i=1;i<=nr;i++)
    {
        k=c[i].size()-1;
        for (j=0;j<=k;j++)
            printf ("%d ", c[i][j]);
        printf ("\n");
    }
    return 0;
}