Cod sursa(job #2417602)

Utilizator danstefanDamian Dan Stefan danstefan Data 30 aprilie 2019 15:08:59
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>
using namespace std;
int m,n,i,x,y,st[100010],k,nr,niv[100010],low[100010];
vector<int>g[100010],ans[100010];
bool ap[100010];
void dsf(int node,int tata)
{
    ap[node]=true;
    st[++k]=node;
    niv[node]=niv[tata]+1;
    low[node]=niv[node];
    for(auto it:g[node])
        if(ap[it]&&it!=tata)low[node]=min(low[node],niv[it]);
        else if(!ap[it])
        {
            dsf(it,node);
            low[node]=min(low[node],low[it]);
            if(low[it]>=niv[node])
            {
                ++nr;
                while(st[k]!=it)ans[nr].push_back(st[k]),--k;
                ans[nr].push_back(node);
                ans[nr].push_back(it);
                --k;
            }
        }
}
int main()
{
    ifstream cin ("biconex.in");
    ofstream cout ("biconex.out");
    cin>>n>>m;
    for(i=1; i<=m; ++i)
    {
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for(i=1; i<=n; ++i)
        if(!ap[i])dsf(i,0);
    cout<<nr<<'\n';
    for(i=1; i<=nr; ++i)
    {
        for(auto &it:ans[i])cout<<it<<" ";
        cout<<'\n';
    }
    return 0;
}