Cod sursa(job #2672065)

Utilizator killerdonuttudor nicolae killerdonut Data 12 noiembrie 2020 23:46:12
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.51 kb
//doar in scop de testare

#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";
   }
}