Cod sursa(job #2528465)

Utilizator GabyD002Dobrita Gabriel GabyD002 Data 21 ianuarie 2020 22:03:46
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
#include <bits/stdc++.h>
#define mp make_pair
#define NM 100005
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");

int n,m,niv[NM],l[NM];
vector <int> v[NM];
vector <vector<int>> c;
stack <pair<int,int>> st;

void DFS(int nod)
{   l[nod]=niv[nod];
    vector <int> :: iterator it;
    for(it=v[nod].begin(); it!=v[nod].end(); it++)
        if(!niv[*it])
        {   niv[*it]=niv[nod]+1;
            st.push(mp(nod,*it));
            DFS(*it);
            l[nod]=min(l[nod],l[*it]);
            if(niv[nod]<=l[*it])
            {   int x=nod,y=(*it);
                vector <int> sol;
                if(st.size()==1)
                {   sol.push_back(st.top().first);
                    sol.push_back(st.top().second);
                    st.pop();
                }
                else
                {   while(st.top().first!=x || st.top().second!=y)
                    {   sol.push_back(st.top().second);
                        st.pop();
                    }
                    sol.push_back(x);
                    sol.push_back(y);
                    st.pop();
                }
                c.push_back(sol);
            }
        }
        else
        if(*it!=nod)
            l[nod]=min(l[nod],niv[*it]);
}

int main()
{   f>>n>>m;
    for(int x,y; f>>x>>y;)
    {   v[x].push_back(y);
        v[y].push_back(x);
    }
    niv[1]=1;
    DFS(1);
    g<<c.size()<<'\n';
    for(int i=0; i<c.size(); i++)
    {   vector <int> :: iterator it;
        for(it=c[i].begin(); it!=c[i].end(); it++)
            g<<(*it)<<' ';
        g<<'\n';
    }
    f.close(); g.close(); return 0;
}