Cod sursa(job #2666173)

Utilizator VladAlexandruAnghelache Vlad VladAlexandru Data 1 noiembrie 2020 04:29:57
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <bits/stdc++.h>

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

stack<pair<int, int>> s;
vector<set<int>> rez;

void DFS(int nod, int low[], int disc[], vector<int> graf[])
{

    static int i=1;
    disc[nod]=i;
    low[nod]=i;
    i++;


    for(int it : graf[nod])
    {
        if(disc[it] == 0)
        {
            s.push({nod,it});
            DFS(it, low, disc,graf);
            low[nod]=min(low[nod],low[it]);
            if(disc[nod]<=low[it])
            {
                set<int> comp;
                int x=s.top().first,y=s.top().second;
                while(!(x==nod&&y==it))
                {
                    s.pop();
                    comp.insert(x);
                    comp.insert(y);
                    x=s.top().first;
                    y=s.top().second;

                }
                s.pop();
                comp.insert(x);
                comp.insert(y);

                rez.push_back(comp);

            }

        }
        else if(disc[it] != 0)
        {
            low[nod]=min(low[nod],disc[it]);

        }

    }
}
int main()
{
    int n,m;
    fin>>n>>m;
    vector<int> graf[n+1];
    int low[n+1]= {0};
    int disc[n+1]= {0};

    while(m--)
    {
        int x,y;
        fin>>x>>y;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }

        DFS(1,low,disc,graf);

    fout<<rez.size()<<"\n";
    for(auto comp: rez)
    {
        for(auto nod:comp)
            fout<<nod<<" ";
        fout<<"\n";
    }
    return 0;
}