Cod sursa(job #2648620)

Utilizator GiosinioGeorge Giosan Giosinio Data 11 septembrie 2020 21:12:20
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
#include <bits/stdc++.h>
#define DIM 100005

using namespace std;

ifstream f("biconex.in");
ofstream g("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){
    f>>N>>M;
    int x, y;
    for(int i=1; i<=M; i++){
        f>>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)
            g<<p->key<<" ";
        g<<"\n";
    }
}

int main()
{
    read(N,M);
    low[1] = niv[1] = 0;
    DFS(1, 0, 0);
    g<<nr_comp<<"\n";
    afisare(nr_comp, C);
}