Cod sursa(job #2666085)

Utilizator anacomoAna-Maria Comorasu anacomo Data 31 octombrie 2020 20:16:08
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.96 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");
stack <pair <int, int>> stiva;
vector<set <int>> components;

void DFS(int node, int parent, int i, vector<int>& depth, vector<int>& lowlink, vector<int> adiacente[])
{
    depth[node] = i;
    lowlink[node] = i;
    for(auto nei : adiacente[node])
        if(nei != parent)
        {
            if(depth[nei] == 0)
            {
                stiva.push(make_pair(node, nei));
                DFS(nei, node, i+1, depth, lowlink, adiacente);

                lowlink[node] = min(lowlink[node], lowlink[nei]);
                if(lowlink[nei] >= depth[node])
                {
                    pair<int, int> topStack;
                    pair<int, int> stopStack = make_pair(node, nei);
                    set<int> component;
                    do
                    {
                        topStack = stiva.top();
                        stiva.pop();
                        component.insert(topStack.first);
                        component.insert(topStack.second);
                    } while (topStack != stopStack);
                    components.push_back(component);
                }
            }
            else
            {
                lowlink[node] = min(lowlink[node], depth[nei]);
            }
            
        }
}

int main()
{
    int n, m;
    fin >> n >> m;
    vector<int> adiacente[n+1];
    vector<int> lowlink(n+1, 0);
    vector<int> depth(n+1, 0);

    for(int i = 0; i < m; ++i)
    {
        int x, y;
        fin >> x >> y;
        adiacente[x].push_back(y);
        adiacente[y].push_back(x);
    }

    for(int i = 1; i <= n; ++i)
        if(depth[i] == 0)
            DFS(i, 0, 1, depth, lowlink, adiacente);

    fout << components.size()<< endl;
    for(int i = 0; i < components.size(); ++i)
    {
        for(auto node : components[i])
            fout << node << " ";
        fout << endl;
    }
    fin.close();
    fout.close();
    return 0;
}