Cod sursa(job #2781445)

Utilizator guzgandemunteIonescu Laura guzgandemunte Data 9 octombrie 2021 16:19:24
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2 kb
#include <bits/stdc++.h>
#include <fstream>
#define VMAX 100000
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");

vector <int> adj[VMAX];
int V, E, x, timp, y;
int disc[VMAX], low[VMAX];
bool artPoint[VMAX];
stack < pair <int, int> > edges;
vector < unordered_set <int> > allBcc(VMAX);
int nrBcc;

void DFSap(int u, int parent = -1)
{
    int children = 0;
    disc[u] = low[u] = ++timp;
    for (auto w : adj[u])
    {
        if (parent == w) continue;
        if (!disc[w])
        {
            edges.push(make_pair(u, w));
            DFSap(w, u);
            low[u] = min(low[u], low[w]);
            if (low[w] >= disc[u])
            {
                while (edges.top() != make_pair(u, w))
                {
                    allBcc[nrBcc].insert(edges.top().first);
                    allBcc[nrBcc].insert(edges.top().second);
                    edges.pop();
                }
                allBcc[nrBcc].insert(edges.top().first);
                allBcc[nrBcc].insert(edges.top().second);
                edges.pop();
                nrBcc++;
            }
        }
        else if (disc[w] < disc[u])
        {
            edges.push(make_pair(u, w));
            low[u] = min(low[u], disc[w]);
        }
    }
}

int main()
{
    fin >> V >> E;

    while (E--)
    {
        fin >> x >> y;
        x--, y--;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    for (int i = 0; i < V; ++i)
    {
        if (!disc[i]) DFSap(i);
        timp = 0;
    }

    fout << nrBcc << endl;

    for (int i = 0; i < V; ++i)
    {
        bool ok = false;
        for (auto j : allBcc[i])
        {
            ok = true;
            fout << j + 1 << " ";
        }
        if (ok) fout << endl;
    }

    fin.close();
    fout.close();

    return 0;
}

/*
5 5
0 2
1 2
1 0
0 3
3 4
*/

/*
5 6
1 2
2 3
1 3
3 4
4 5
5 3
*/

/*
8 9
1 2
2 3
3 4
4 1
1 5
5 6
6 7
7 5
7 8
*/