Cod sursa(job #2453418)

Utilizator Anastasia11Susciuc Anastasia Anastasia11 Data 3 septembrie 2019 18:26:58
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#define fs first
#define sc second
#define pii pair <int, int>
#define Nmax 100005

using namespace std;

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

int n, m, comp_bicon;
bool used[Nmax];
int lvl[Nmax], low[Nmax];
vector <int> v[Nmax], sol[Nmax];
stack <int> stk;

void dfs(int x, int lv)
{
    used[x]=1;
    lvl[x]=low[x]=lv;
    stk.push(x);
    for (auto y:v[x])
    {
        if (used[y] == 1) low[x]=min(low[x], lvl[y]);
        else
        {
            dfs(y, lv+1);

            if (lvl[x] <= low[y])
            {
                comp_bicon++;
                while (stk.top()!=y)
                {
                    sol[comp_bicon].push_back(stk.top());
                    stk.pop();
                }
                sol[comp_bicon].push_back(stk.top());
                sol[comp_bicon].push_back(x);
                stk.pop();
            }
            low[x]=min(low[x], low[y]);
        }
    }
}

int main()
{
    f >> n >> m;
    for (int i = 1, x, y; i <= m; i++)
    {
        f >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1, 1);

    g << comp_bicon << '\n';
    for (int i = 1; i <= comp_bicon; i++)
    {
        for (auto j:sol[i]) g << j << " ";
        g << '\n';
    }

    return 0;
}