Cod sursa(job #2899948)

Utilizator betybety bety bety Data 9 mai 2022 19:20:52
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <bits/stdc++.h>

using namespace std;

const int DIM = 100005;

ifstream in("biconex.in");

ofstream out("biconex.out");

struct node

{

    int key;

    node *next;

}*L[DIM];

int N, M;

int low[DIM], niv[DIM];

stack <pair <int, int> > stk;

node *C[DIM];

int nr_comp;

void add(int x, int y, node *l[])

{

    node *p = new node;

    p->key = y;

    p->next = l[x];

    l[x] = p;

}

void read(int &N, int &M)

{

    in>>N>>M;

    int x, y;

    for(int i=1; i<=M; i++)

    {

        in>>x>>y;

        add(x,y,L);

        add(y,x,L);

    }

}

void c_bic(int x, int y, int indice)

{

    int tx, ty;

    do

    {

        tx = stk.top().first, ty = stk.top().second;

        stk.pop();

        add(indice, ty, C);

    }

    while(tx != x && ty != y);

    add(indice, x, C);

}

void DFS(int x, int fx, int level)

{


    niv[x] = low[x] = level;

    for(node *p = L[x]; p != nullptr; p = p->next)

    {

        if(p->key == fx)

            continue;

        if(niv[p->key] == 0)

        {

            stk.push(make_pair(x, p->key));

            DFS(p->key, x, level+1);

            low[x] = min(low[x], low[p->key]);

            if(niv[x] <= low[p->key])

            {

                c_bic(x,p->key, nr_comp);

                nr_comp++;

            }

        }

        else

            low[x] = min(low[x], niv[p->key]);

    }

}

void afisare(int lung, node *l[])

{

    for(int i=0; i<lung; ++i)

    {

        for(node *p = l[i]; p != nullptr; p = p->next)

            out<<p->key<<" ";

        out<<"\n";

    }

}

int main()

{

    read(N,M);

    low[1] = niv[1] = 0;

    DFS(1, 0, 0);

    out<<nr_comp<<"\n";

    afisare(nr_comp, C);

}