Cod sursa(job #3005496)

Utilizator SabailaCalinSabaila Calin SabailaCalin Data 17 martie 2023 00:55:44
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int SIZE = 100005;

int n, m, id, cnt;
int low[SIZE], ids[SIZE];

vector <int> adj[SIZE];
vector <int> bicc[SIZE];

stack <int> s;

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

void AddToBicc(int node, int neighbour)
{
    cnt++;
    while (s.top() != neighbour)
    {
        bicc[cnt].push_back(s.top());
        s.pop();
    }
    bicc[cnt].push_back(node);
    bicc[cnt].push_back(neighbour);
    s.pop();
}

void DFS(int node, int par = -1)
{
    low[node] = ids[node] = ++id;
    s.push(node);

    for (unsigned int i = 0; i < adj[node].size(); i++)
    {
        int neighbour = adj[node][i];

        if (neighbour == par)  continue;

        if (low[neighbour] != 0)
        {
            low[node] = min(low[node], ids[neighbour]);
        }
        else
        {
            DFS(neighbour, node);
            low[node] = min(low[node], low[neighbour]);

            if (low[neighbour] >= ids[node])
            {
                AddToBicc(node, neighbour);
            }
        }
    }
}

void Solve()
{
    for (int i = 1; i <= n; i++)
    {
        if (low[i] == 0)
        {
            DFS(i);
        }
    }
}

void Print()
{
    for (int i = 1; i <= n; i++)
    {
        for (unsigned int j = 0; j < bicc[i].size(); j++)
        {
            g << bicc[i][j] << " ";
        }
        g << "\n";
    }
}

int main()
{
    Read();
    Solve();
    Print();

    return 0;
}