Cod sursa(job #2844044)

Utilizator TiberiwTiberiu Amarie Tiberiw Data 3 februarie 2022 17:47:17
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <bits/stdc++.h>
#define Dmax 100005
using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");
int n,m,niv[Dmax],nma[Dmax],nrc;
vector <int> G[Dmax],sol[Dmax];
stack <int> S;

void DFS(int nod,int tata)
{
    niv[nod]=nma[nod]=niv[tata]+1;
    S.push(nod);
    for(vector<int>::iterator it = G[nod].begin(); it < G[nod].end(); it++)
    {
        if(*it==tata)
            continue;
        if(niv[*it])
            nma[nod]=min(nma[nod],niv[*it]);
        else
        {
            DFS(*it,nod);
            nma[nod] = min(nma[nod],nma[*it]);
            if(niv[nod] <= nma[*it])
            {
                nrc++;
                while(S.top()!=*it)
                {
                    sol[nrc].push_back(S.top());
                    S.pop();
                }

                sol[nrc].push_back(S.top());
                    S.pop();
                sol[nrc].push_back(nod);





            }



        }


    }


}

int main()
{
    f>>n>>m;
    for(int i = 1; i <= m; i++)
    {
        int x,y;
        f>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }


        for(int i = 1; i <= n; i++)
            if(!niv[i])
            DFS(i,i);

        g<<nrc<<"\n";
        for(int i = 1; i <= nrc; i++,g<<"\n")
            for(vector<int>::iterator it = sol[i].begin(); it < sol[i].end(); it++)
                g<<*it<<" ";


    return 0;
}