Cod sursa(job #2285294)

Utilizator savulescustefanSavulescu Stefan savulescustefan Data 18 noiembrie 2018 13:57:37
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.05 kb
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
vector <int> c[100004],v[100004];
vector < pair<int,int> > s;
int n,m,i,j,k,x,y,nr,poz,d[100004],l[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;
            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, int y)
{
    nr++;
    poz=s.size()-1;
    while ((s[poz].first!=x) || (s[poz].second!=y))
    {
        c[nr].push_back(s[poz].first);
        c[nr].push_back(s[poz].second);
        s.pop_back();
        poz--;
    }
    c[nr].push_back(s[poz].first);
    c[nr].push_back(s[poz].second);
    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({x,v[x][i]});
            p(v[x][i]);
            if (l[x]<=d[v[x][i]])
                r(x,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++)
    {
        sort (c[i].begin(),c[i].end());
        printf ("%d ", c[i][0]);
        k=c[i].size()-1;
        for (j=1;j<=k;j++)
        {
            if (c[i][j]!=c[i][j-1])
                printf ("%d ", c[i][j]);
        }
        printf ("\n");
    }
    return 0;
}