Cod sursa(job #2657883)

Utilizator stanbianca611Stan Bianca stanbianca611 Data 12 octombrie 2020 16:12:46
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.48 kb
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

ifstream f ("biconex.in");
ofstream g ("biconex.out");

vector<int> v[100005], dft, low;
vector <vector <int>> c;
stack <pair <int, int> > sk;
int n, m;

void punct_de_articulatie(int x, int y)
{
    vector<int> con;
    int tx, ty;
    //toti copiii lui x din stiva fac parte din componenta conexa
    while(tx != x || ty!=y)
    {
        tx=sk.top().first;
        ty=sk.top().second;
        sk.pop();
        con.push_back(tx);
        con.push_back(ty);
    }
    c.push_back(con);
}

void DFS (int x, int parent, int k)
{
    dft[x]=k;
    low[x]=k;
    for(int i=0; i<v[x].size(); i++)//parcurc toti vecinii lui x
    {
        //conditia 1: nu o iau pe muchii de intoarcere
        //conditia 2: vecinul nu este vizitat
        if(v[x][i]!=parent && dft[v[x][i]]==-1)
        {
            //pun muchia pe care ma duc in stiva
            sk.push(make_pair(x, v[x][i]));
            DFS(v[x][i], x, k+1);//fac dfs pe vecinul ales
            //daca copiii lui x au tutut sa ajunga intr-un nod doar prin o muchie de intparcere
            //inseamna ca si x poate, coborand putin si luand acceas muchie
            low[x]=min(low[x], low[v[x][i]]);
            if(low[v[x][i]]>=dft[x])//contitia ca x sa fie punct de articulatie
                punct_de_articulatie(x, v[x][i]);
        }
        else if(dft[v[x][i]]!=-1)//daca nodul e deja vizitat inseamna ca asta e o muchie de intoarcere
        {
            low[x]=min(low[x], dft[v[x][i]]);//asa ca fac update la low
        }
    }
}

int main()
{
    f>>n>>m;//citest nr de noduri si de muchii
    for(int i=0; i<m; i++)//citesc toae muchiile si le pun in lista de adiacenta
    {
        int x, y;
        f>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dft.resize(n+1);//dft[x] va fi al catelea nod a fost x in parcurgerea dfs
    dft.assign(n+1, -1);//deocamdata toatenodurile au valoarea -1, adica nu au fost vizitate
    low.resize(n+1);//low[x] va fi dft[p] unde p este cel mai  de sus nod la care se poate ajunge
    //din x, traversand doar o muchie de intoarcere

    DFS(1, 0, 0);

    g<<c.size()<<"\n";
    for(int i=0; i< c.size(); i++)
    {
        sort( c[i].begin(), c[i].end() );
        c[i].erase( unique( c[i].begin(), c[i].end() ), c[i].end() );
        for(int j=0; j<c[i].size(); j++)
        {
            g<<c[i][j]<<" ";
        }
        g<<"\n";
    }
    return 0;
}