Cod sursa(job #2578946)

Utilizator RedXtreme45Catalin RedXtreme45 Data 11 martie 2020 19:02:33
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <fstream>
#include <stack>
#include <vector>
#define Nmax 100001
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n,m,niv[Nmax],nivmin[Nmax],nr;
vector <int> G[Nmax],sol[Nmax];
stack <int> s;
void DFS(int nod,int str)
{
    niv[nod]= nivmin[nod]=niv[str]+1;
    s.push(nod);
    for (auto i:G[nod])
    {
        if (i!=str)
        {
            if (niv[i]==0)
            {
                DFS(i,nod);
                nivmin[nod]=min(nivmin[nod],nivmin[i]);
                if (niv[nod]<=nivmin[i])
                {
                    int x=s.top();
                    s.pop();
                    while (x!=i)
                    {
                        sol[nr].push_back(x);
                        x=s.top();
                        s.pop();
                    }
                    sol[nr].push_back(i);
                    sol[nr].push_back(nod);
                    nr++;
                }
            }
            else
            nivmin[nod]=min(nivmin[nod],niv[i]);
        }
    }
}
int main()
{
    int i,a,b;
    fin>>n>>m;
    for (i=1; i<=m; i++)
    {
        fin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    DFS(1,0);
    fout<<nr<<"\n";
    for (int j=0;j<nr;j++)
    {
        for (auto i:sol[j])
            fout<<i<<" ";
        fout<<"\n";
    }
    return 0;
}