Cod sursa(job #3196655)

Utilizator RobertAcAcatrinei Robert-Marian RobertAc Data 24 ianuarie 2024 15:26:48
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.84 kb
#include <bits/stdc++.h>
#ifdef LOCAL
#define in cin
#define out cout
#endif

using namespace std;

#ifndef LOCAL
ifstream in("biconex.in");
ofstream out("biconex.out");
#endif

const int nmax = 1e5 + 5;

vector<int> adj[nmax];
int depth[nmax];
int low[nmax];
stack<int> s;
vector<vector<int>> comps;

void dfs(int nod = 1, int p = 0, int d = 1)
{
    s.push(nod);
    int fii = 0;
    bool isart = 0;
    low[nod] = depth[nod] = d;
    for (auto i : adj[nod])
    {
        if (i == p)
        {
            // tatal
            continue;
        }
        else if (depth[i] != 0 && depth[i] < depth[nod])
        {
            // muchie de intoarcere
            low[nod] = min(low[nod], depth[i]);
            continue;
        }
        else if (depth[i] == 0)
        {
            // nod nevizitat/muchie normala
            fii++;
            dfs(i, nod, d + 1);
            low[nod] = min(low[nod], low[i]);
            if (low[i] >= depth[nod]) // daca fii din subarbore nu pot ajunge mai sus de nod
            {
                // este punct de articulatie
                isart = 1;
                // se goleste stack-ul pana la i inclusiv
                vector<int> tmp;
                while (!s.empty() && s.top() != i)
                {
                    tmp.push_back(s.top());
                    s.pop();
                }
                tmp.push_back(s.top());
                s.pop();
                tmp.push_back(nod);
                comps.push_back(tmp);
            }
        }
    }
}

int main()
{
    int n, m;
    in >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        in >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs();
    out << comps.size() << '\n';
    for (auto i : comps)
    {
        for (int j : i)
        {
            out << j << ' ';
        }
        out << '\n';
    }
}