Cod sursa(job #1830523)

Utilizator Vlad1111Sbengheci Vlad-Andrei Vlad1111 Data 16 decembrie 2016 20:10:01
Problema Componente biconexe Scor 42
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#define cout cerr
#define MAX 100005
using namespace std;

int n,m,x,y;
int nivel[MAX],nivel_max[MAX];
int nrn;
vector <int> grf[2*MAX];
vector <int> conex[MAX];
stack <int> tat;

void DFS(int k,int t)
{
    nivel[k]=nivel[t]+1;
    nivel_max[k]=nivel[k];

    for(int i=0; i<grf[k].size(); i++)
        if(grf[k][i]!=t)
        {
            if(nivel[grf[k][i]]==0)
            {
                tat.push(grf[k][i]);
                DFS(grf[k][i],k);
                if(nivel_max[grf[k][i]]>=nivel[k])
                {
                    while(tat.top()!=k && !tat.empty())
                    {
                        conex[nrn].push_back(tat.top());
                        tat.pop();
                    }
                    conex[nrn].push_back(k);
                    nrn++;
                }
            }
            nivel_max[k]=min(nivel_max[k],nivel_max[grf[k][i]]);
        }
}

int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);

    scanf("%d %d",&n,&m);

    for(int i=0; i<m; i++)
    {
        scanf("%d %d",&x,&y);
        grf[x].push_back(y);
        grf[y].push_back(x);
    }


    tat.push(1);
    DFS(1,1);

    printf("%d\n",nrn);
    for(int i=0; i<=nrn; i++)
    {
        for(int j=0;j<conex[i].size();j++)
            printf("%d ",conex[i][j]);
        printf("\n");
    }
    return 0;
}