Cod sursa(job #2407927)

Utilizator SchnitzelMannPavaloiu Gabriel SchnitzelMann Data 17 aprilie 2019 12:49:53
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
vector<int> v[100002],c[100002];
int l[100002],a[100002],N;
stack<int> s;
void bitconnet(int nr)
{
    s.push(nr);
    for(auto it:v[nr])
        if(!l[it])
        {
            l[it]=a[it]=l[nr]+1;
            bitconnet(it);
            a[nr]=min(a[nr],a[it]);
            if(a[it]>=l[nr])
            {
                c[++N].push_back(nr);
                while(!s.empty())
                {
                    c[N].push_back(s.top());
                    if(s.top()==it)
                    {
                        s.pop();
                        break;
                    }
                    s.pop();
                }
            }
        }
        else
            a[nr]=min(a[nr],l[it]);
}
int main()
{
    int n,m,i,j;
    in>>n>>m;
    while(m--)
    {
        in>>i>>j;
        v[i].push_back(j);
        v[j].push_back(i);
    }
    l[1]=a[1]=1;
    bitconnet(1);
    out<<N<<"\n";
    for(i=1;i<=N;i++)
    {
        for(auto it:c[i])
            out<<it<<" ";
        out<<"\n";
    }
    return 0;
}