Cod sursa(job #2576606)

Utilizator BogdanGhGhinea Bogdan BogdanGh Data 6 martie 2020 20:52:59
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
const int nmax=100005;
vector <int>v[nmax],ans[nmax];
stack <pair <int,int>>s;
bool viz[nmax];
int n,m,x,y,i,l[nmax],nv[nmax],nr,r,sol;
void dfs(int nod,int p)
{
    viz[nod]=1;
    l[nod]=nv[nod]=++nr;
    for(auto i:v[nod])
    {
        if(i==p)continue;
        if(!viz[i])
        {
            s.push({nod,i});
            dfs(i,nod);
            if(l[nod]>l[i])l[nod]=l[i];
            if(l[i]>=nv[nod]&&nod!=r)
            {
                sol++;
                while(!s.empty()&&!(s.top().first==nod && s.top().second==i))
                {
                    ans[sol].push_back(s.top().first);
                    ans[sol].push_back(s.top().second);
                    s.pop();
                }
                if(!s.empty())
                {
                    ans[sol].push_back(s.top().first);
                    ans[sol].push_back(s.top().second);
                    s.pop();
                }
            }

            }
        else l[nod]=min(l[i],l[nod]);
    }
}
int main()
{
    f>>n>>m;
    for(i=1; i<=m; i++)
    {
        f>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0);
    g<<sol<<'\n';
    for(i=1;i<=sol;i++)
    {
        sort(ans[i].begin(),ans[i].end());
        g<<ans[i][0]<<' ';
        for(int j=1;j<ans[i].size();j++)
            if(ans[i][j]!=ans[i][j-1])
            g<<ans[i][j]<<' ';
        g<<'\n';
    }
    return 0;
}