Cod sursa(job #2721656)

Utilizator valentinchipuc123Valentin Chipuc valentinchipuc123 Data 12 martie 2021 02:57:52
Problema Componente biconexe Scor 46
Compilator cpp-64 Status done
Runda no-time-to-rest-v2 Marime 1.57 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");

int n,m,inapoi[100005],grad[100005],nr=0,tr=0,stiva[100005];
bool fost[100005];
vector<int>vecini[100005],sol[100005];

void dfs(int nod,int tata)
{
    grad[nod]=grad[tata]+1;
    inapoi[nod]=grad[nod];

    for(int i=0; i<vecini[nod].size(); i++)
    {
        int x=vecini[nod][i];

        if( x!=tata&&grad[x]==0 )
        {
            dfs(x,nod);
            inapoi[nod]=min(inapoi[nod],inapoi[x]);
        }
        else if( x!=tata ) inapoi[nod]=min(inapoi[nod],grad[x]);
    }
}

void dfs_solve(int nod,int tata)
{
    fost[nod]=1;
    stiva[++nr]=nod;
    int ct=0;

    for(int i=0; i<vecini[nod].size(); i++)
    {
        int x=vecini[nod][i];

        if( fost[x]==0 )
        {
            ct++;
            dfs_solve(x,nod);

            if( grad[nod]<=inapoi[x] )
            {
                tr++;
                while( nr>0&&stiva[nr]!=nod )
                {
                    sol[tr].push_back(stiva[nr]);
                    nr--;
                }
                sol[tr].push_back(stiva[nr]);
            }
        }
    }
}

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

    dfs(1,0);

    dfs_solve(1,0);
    g<<tr<<'\n';
    for(int i=1; i<=tr; i++)
    {
        for(int j=0; j<sol[i].size(); j++)
        {
            g<<sol[i][j]<<' ';
        }
        g<<'\n';
    }
}