Cod sursa(job #2809261)

Utilizator rimihaiMihai Radu-Ioan rimihai Data 26 noiembrie 2021 15:07:27
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.86 kb
#include<bits/stdc++.h>

using namespace std;

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

vector<int> lista_adiacenta[100001];
unordered_map<int,int> vizitat;
vector <set <int>> componente;
stack<pair<int, int>> stackCBC;
int low[100001]= {0};
int timp;
int n;

void biconex(int start, int prev)
{

    timp++;
    vizitat[start] = timp;
    low[start] = timp;
    /*cout<<"LOW"<<endl;
    for(int i=1; i<=n; i++)
    {
        cout<<low[i]<<endl;
    }*/
    for (int i=0; i<lista_adiacenta[start].size(); i++)
    {
        if (vizitat[lista_adiacenta[start][i]]==0)
        {
            stackCBC.push({start, lista_adiacenta[start][i]});
            //cout<<"1 "<<start<<" "<<lista_adiacenta[start][i]<<endl;
            biconex(lista_adiacenta[start][i], start);
            //cout<<"2 "<<start<<" "<<lista_adiacenta[start][i]<<endl;
            low[start] = min(low[lista_adiacenta[start][i]],low[start]);
            if (low[lista_adiacenta[start][i]]>=vizitat[start])
            {
                //cout<<"2 "<<low[lista_adiacenta[start][i]]<<" "<<vizitat[start]<<endl;
                set<int> elem;
                int elem1,elem2;
                elem1 = stackCBC.top().first;
                elem2 = stackCBC.top().second;
                elem.insert(elem1);
                elem.insert(elem2);
                stackCBC.pop();
                //cout<<"XXX "<<start<<" "<<lista_adiacenta[start][i]<<" "<<elem1<<" "<<elem2<<endl;
                while (elem1 != start || elem2 != lista_adiacenta[start][i])
                {
                    elem1 = stackCBC.top().first;
                    elem2 = stackCBC.top().second;
                    elem.insert(elem1);
                    elem.insert(elem2);
                    stackCBC.pop();
                    //cout<<elem1<<" "<<elem2<<endl;
                    //cout<<"XXX2 "<<start<<" "<<lista_adiacenta[start][i]<<" "<<elem1<<" "<<elem2<<endl;
                }
                componente.push_back(elem);
                //cout<<endl;
            }
        }
        else if (lista_adiacenta[start][i]!=prev)
        {
            low[start] = min(vizitat[lista_adiacenta[start][i]],low[start]);
        }
    }
}

int main()
{
    int m,x,y;
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);
    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);
    }
    //cout<<endl;
    biconex(1,0);
    fout<< componente.size() <<'\n';

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

    /*cout<<"LOW"<<endl;
    for(int i=1; i<=n; i++)
    {
        cout<<low[i]<<endl;
    }*/
    return 0;
}