Cod sursa(job #3210137)

Utilizator BuzdiBuzdugan Rares Andrei Buzdi Data 5 martie 2024 11:14:26
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.73 kb
#include <fstream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>

using namespace std;

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

const int NMAX = 1e5;

int n, m, indst, curentTime;
vector<int> G[NMAX + 1];
pair<int, int> st[NMAX + 1];
vector<vector<int>> GCC;

int DFSTime[NMAX + 1];
int low[NMAX + 1];

void GetBCC(int down, int up)
{
    vector<int> C;
    int curDown, curUp;
    do
    {
        curDown = st[indst].first;
        curUp = st[indst].second;
        C.push_back(curDown);
        C.push_back(curUp);

        indst--;
    }while(down != curDown || up != curUp);

    sort(C.begin(), C.end());
    C.erase(unique(C.begin(), C.end()), C.end());
    GCC.push_back(C);
}

void DFS(int node, int dad)
{
    DFSTime[node] = low[node] = ++curentTime;
    for(int nextNode : G[node])
    {
        if(nextNode != dad && DFSTime[nextNode] < DFSTime[node])
            st[++indst] = make_pair(nextNode, node);

        if(!DFSTime[nextNode])
        {
            DFS(nextNode, node);
            low[node] = min(low[node], low[nextNode]);

            if(low[nextNode] >= DFSTime[node])
                GetBCC(nextNode, node);
        }
        else
            low[node] = min(low[node], DFSTime[nextNode]);
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    for(int i = 1; i <= n; i++)
        if(!DFSTime[i])
            DFS(i, 0);

    cout << GCC.size() << '\n';
    for(int i = 0; i < (int) GCC.size(); i++, cout << '\n')
        for(int x : GCC[i])
            cout << x << ' ';

    return 0;
}