Cod sursa(job #2797902)

Utilizator rimihaiMihai Radu-Ioan rimihai Data 10 noiembrie 2021 18:47:55
Problema Componente biconexe Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.97 kb
#include<bits/stdc++.h>

using namespace std;

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

vector<int> lista_adiacenta[10005];
unordered_map<int,int> vizitat;
vector <set <int>> componente;
stack<pair<int, int>> stackCBC;
int low[100005]={0};
int timp,elem1,elem2;

void biconex(int start)
{
    timp++;
    vizitat[start] = timp;
    low[start] = timp;
    for (int i=0; i<lista_adiacenta[start].size(); i++)
    {
        if (vizitat[lista_adiacenta[start][i]]==0)
        {
            stackCBC.push({start, lista_adiacenta[start][i]});
            biconex(lista_adiacenta[start][i]);
            low[start] = min(low[lista_adiacenta[start][i]],low[start]);
            if (low[lista_adiacenta[start][i]]>=vizitat[start])
            {
                set<int> elem;
                elem1 = stackCBC.top().first;
                elem2 = stackCBC.top().second;
                elem.insert(elem1);
                elem.insert(elem2);
                stackCBC.pop();
                while (elem1 != start || elem2 != lista_adiacenta[start][i])
                {
                    elem1 = stackCBC.top().first;
                    elem2 = stackCBC.top().second;
                    elem.insert(elem1);
                    elem.insert(elem2);
                    stackCBC.pop();
                }
                componente.push_back(elem);
            }
        }
        else
        {
            low[start] = min(vizitat[lista_adiacenta[start][i]],low[start]);
        }
    }
}

int main()
{
    int n,m,x,y;
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        fin>>x>>y;
        lista_adiacenta[x].push_back(y);
        lista_adiacenta[y].push_back(x);
    }
    biconex(1);
    fout<< componente.size() <<'\n';

    for (auto cbc: componente)
    {
        set<int>::iterator it;
        for (it = cbc.begin(); it != cbc.end(); it++)
            fout << *it << " ";
        fout << "\n";
    }
    return 0;

}