Cod sursa(job #2882875)

Utilizator valentinchipuc123Valentin Chipuc valentinchipuc123 Data 31 martie 2022 21:21:14
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <bits/stdc++.h>

using namespace std;

int n,m,mn[100005],niv[100005],nr;
vector<int>vecini[100005];
stack< pair<int,int> > muchii;
vector<int>ans[100005];

void componenta(int a,int b)
{
    vector<int>elem;
    while(!muchii.empty())
    {
        int x=muchii.top().first;
        int y=muchii.top().second;
        muchii.pop();
        elem.push_back(x);
        elem.push_back(y);
        if(x==a&&y==b) break;
    }
    sort(elem.begin(),elem.end());
    nr++;
    ans[nr].push_back(elem[0]);
    for(int i=1; i<elem.size(); i++)
        if(elem[i]!=elem[i-1]) ans[nr].push_back(elem[i]);
}

void dfs(int nod,int tata)
{
    niv[nod]=niv[tata]+1;
    mn[nod]=niv[nod];

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

        if(niv[x]==0)
        {
            muchii.push({nod,x});
            dfs(x,nod);
            mn[nod]=min(mn[nod],mn[x]);

            if(mn[x]>=niv[nod]) componenta(nod,x);
        }
        else
        {
            mn[nod]=min(mn[nod],niv[x]);
        }
    }
}

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

    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);
    g<<nr<<'\n';
    for(int i=1; i<=nr; i++)
    {
        for(int j=0; j<ans[i].size(); j++)
            g<<ans[i][j]<<' ';
        g<<'\n';
    }

    f.close();
    g.close();

    return 0;
}