Cod sursa(job #2481652)

Utilizator PetrescuAlexandru Petrescu Petrescu Data 27 octombrie 2019 10:44:30
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.76 kb
#include <fstream>
#include <vector>
#include <stack>
#include <utility>
#include <algorithm>
#define MAX 100001

using namespace std;

vector<int> graph[MAX];
vector<vector<int>>compB;
stack<pair<int, int>> stiva;
int up[MAX], low[MAX];
bool vizitat[MAX];

void cleanStack(pair<int, int> pairN)
{
    vector<int> subgraf;
    int nx, ny;

    do
    {
        nx = stiva.top().first;
        ny = stiva.top().second;

        stiva.pop();
        subgraf.push_back(nx);
        subgraf.push_back(ny);
    }while(nx != pairN.first || ny != pairN.second);

    compB.push_back(subgraf);
}

void DFS(int nod, int father, int id)
{
    up[nod] = low[nod] = id;

    for(auto vecin : graph[nod])
    {
        if(vecin != father && !vizitat[vecin])
        {
            vizitat[vecin] = 1;
            stiva.push({nod, vecin});
            DFS(vecin, nod, id + 1);

            low[nod] = min(low[nod], low[vecin]);

            if(low[vecin] >= up[nod])cleanStack({nod, vecin});
        }
        else if(vecin != father && vizitat[vecin])
        {
            low[nod] = min(low[nod], up[vecin]);
        }
    }
}
int main()
{
    int n, m, a, b, i;

    ifstream fin("biconex.in");
    ofstream fout("biconex.out");

    fin >> n >> m;

    for(i = 1; i <= m; i++)
    {
        fin >> a >> b;

        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    DFS(1, 0, 0);

    fout << compB.size() << '\n';

    for(auto subgraf : compB)
    {
        sort(subgraf.begin(), subgraf.end());
        subgraf.erase(unique(subgraf.begin(), subgraf.end()), subgraf.end());
        for(auto nod : subgraf)fout << nod << " ";

        fout << '\n';
    }

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

    return 0;
}