Cod sursa(job #2843815)

Utilizator TiberiwTiberiu Amarie Tiberiw Data 2 februarie 2022 23:14:00
Problema Componente biconexe Scor 52
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.88 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],cnt;
bool viz[Dmax];
vector <int> G[Dmax],p_crit,sol[Dmax];
vector < pair <int,int> > m_crit;
stack <int> S,S1;

void DFS(int nod,int tata)
{
    viz[nod] = true;
    niv[nod] = niv[tata]+1;
    nma[nod] = niv[nod];
    S.push(nod);
   // S1.push(nod);
    for(vector<int>::iterator it = G[nod].begin(); it != G[nod].end(); it++)
        if(*it!=tata)
        {
            if(viz[*it])
            {

                nma[nod]=min(nma[nod],niv[*it]);
            }

        else
        {

                DFS(*it,nod);
            nma[nod] = min(nma[nod],nma[*it]);

            if(niv[nod] <= nma[*it] && nod!=1)
            p_crit.push_back(nod);
            if(niv[nod] < nma[*it])
            m_crit.push_back({nod,*it});
            if(niv[nod] <= nma[*it])
            {

                ++cnt;
                while(S.top()!=*it)
                {

                    int x = S.top();
                    sol[cnt].push_back(x);
                    S.pop();
                }

                int x = S.top();
                    sol[cnt].push_back(x);
                    S.pop();
                    x = S.top();
                    sol[cnt].push_back(x);




            }

        }

        }


}


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++)
    sort(G[i].begin(),G[i].end());
    for(int i = 1; i<= n; i++)
        if(!viz[i])
            DFS(i,0);

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

    return 0;
}