Cod sursa(job #2698945)

Utilizator Mirela_MagdalenaCatrina Mirela Mirela_Magdalena Data 23 ianuarie 2021 11:54:30
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#define NMAX 100005
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

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


int n, m;
int lvl[NMAX];
int low[NMAX];
vector<int> G[NMAX];
stack<pair<int, int> > S;
vector<vector<int> > comp;

void get_comp(pair<int, int> edge)
{
    vector<int> temp_comp;

    while (true)
    {
        pair <int, int> tp = S.top();
        S.pop();
        temp_comp.push_back(tp.first);
        temp_comp.push_back(tp.second);

        if (tp == edge)
            break;
    }

    sort(temp_comp.begin(), temp_comp.end());
    temp_comp.erase(unique(temp_comp.begin(), temp_comp.end()), temp_comp.end());

    comp.push_back(temp_comp);

    temp_comp.clear();
}

void DFS(int node = 1, int parent = 0)
{
    low[node] = lvl[node] = lvl[parent] + 1;

    for (auto v:G[node])
    {
        if (v == parent)
            continue;
        if (!lvl[v])
        {
            S.push({node, v});
            DFS(v, node);

            low[node] = min(low[node], low[v]);
            if (low[v] >= lvl[node])
                get_comp({node, v});
        }
        else
            low[node] = min(low[node], lvl[v]);
    }
}

void read()
{
    int x, y;
    f>>n>>m;
    for(int i = 1; i <= m; ++i)
    {
        f>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
}



int main()
{
    read();
    DFS();

   // for(int i = 1; i <= n; ++i)
   //     g<<low[i]<<" ";
   // g<<'\n';

    g<<comp.size()<<'\n';
    for (auto& c:comp)
    {
        for (auto v:c)
            g<<v<<' ';
        g<<'\n';
    }
    return 0;
}