Cod sursa(job #2900101)

Utilizator betybety bety bety Data 10 mai 2022 10:47:17
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <bits/stdc++.h>
#define DIM 100005
using namespace std;
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)
{
    //x = nod curent, fx = father(x);
    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]); //unde x - p->key este muchie de intoarcere in dfs
    }
}
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);
}