Cod sursa(job #2161949)

Utilizator marcdariaDaria Marc marcdaria Data 11 martie 2018 22:13:05
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <vector>
#include <set>
#include <stack>
using namespace std;
 
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
 
const int Dim = 1e5 + 5;
 
 
int m, n, K;     // K - nr comp biconexe
vector <int> G[Dim];
int niv[Dim], L[Dim];
stack <pair<int, int> > s;
set<int> comp[Dim];
 

void Extract(int x, int y) 
{
    int xs, ys;
    do 
    {
        xs = s.top().first; ys = s.top().second;
      
        comp[K].insert (xs);
        comp[K].insert (ys);
        s.pop();
    } while (xs != x || ys != y);
}

int nv;
 
void Dfs(int x, int tata) 
{
    L[x] = niv[x] = ++nv;
    for (const int& y : G[x]) 
    {
        if (y == tata)
            continue;
        if (!niv[y])  // fiu nevizitat
        {
            s.push ({x, y});
            Dfs (y, x);
            L[x] = min(L[x], L[y]);
            if (L[y] >= niv[x])
                K++, Extract(x, y);
        }
        else
            L[x] = min(L[x], niv[y]);
    }
}
 
int main() 
{
    fin >> n >> m;
    for (int x, y, i = 0; i < m; ++i) 
    {
        fin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    Dfs (1, 0);
    fout << K << "\n";
    for (int i = 1; i <= K; ++i) 
    {
        for (const int& node : comp[i])
            fout << node << " ";
        fout << "\n";
    }
}