Cod sursa(job #2808003)

Utilizator rapidu36Victor Manz rapidu36 Data 24 noiembrie 2021 14:08:48
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.93 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

const int N = 1e5 + 1;

vector <int> a[N];
vector <vector<int>> cbc;
stack <pair <int, int>> stiva;
int primul[N], timp[N], t;

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

void dfs(int x)
{
    timp[x] = ++t;
    primul[x] = timp[x];
    for (auto y: a[x])
    {
        if (timp[y] == 0)
        {
            stiva.push({x, y});
            dfs(y);
            primul[x] = min(primul[x], primul[y]);
            if (primul[y] >= timp[x])///am o comp. biconexa care incepe in x
            {
                vector <int> comp;
                while (!stiva.empty() && (stiva.top().first != x || stiva.top().second != y))
                {
                    comp.push_back(stiva.top().first);
                    comp.push_back(stiva.top().second);
                    stiva.pop();
                }
                comp.push_back(stiva.top().first);
                comp.push_back(stiva.top().second);
                stiva.pop();
                cbc.push_back(comp);
            }
        }
        else
        {
            primul[x] = min(primul[x], timp[y]);
        }
    }
}

void scrie_comp()
{
    out << cbc.size() << "\n";
    for (auto c: cbc)
    {
        sort(c.begin(), c.end());
        out << c[0];
        for (size_t i = 1; i < c.size(); i++)
        {
            if (c[i] != c[i-1])
            {
                out << " " << c[i];
            }
        }
        out << "\n";
    }
}

int main()
{
    int n, m;
    in >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int x, y;
        in >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    in.close();
    for (int i = 1; i <= n; i++)
    {
        if (timp[i] == 0)
        {
            dfs(i);
        }
    }
    scrie_comp();
    out.close();
    return 0;
}