Cod sursa(job #2671756)

Utilizator mihai_radulescuMihai Radulescu mihai_radulescu Data 12 noiembrie 2020 17:34:24
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.46 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";
   }
}