Cod sursa(job #2261744)

Utilizator tifui.alexandruTifui Ioan Alexandru tifui.alexandru Data 16 octombrie 2018 17:02:33
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <bits/stdc++.h>
#define Nmax 100001
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
list <int> G[Nmax];
int dfn[Nmax];
int low[Nmax];
vector < vector <int> > comp_bic;
stack < pair <int,int> > st;
vector <int> v;
int n,m,N,xx,yy;
void DFS(int x, int root)
{
    low[x]=dfn[x]=++N;
    for(const auto &it:G[x])
        if(it!=root)
        {
            if(dfn[it]==-1)
            {
                st.push({x,it});
                DFS(it,x);
                low[x]=min(low[x],low[it]);
                if(low[it]>=dfn[x])
                {
                    do
                    {
                        xx=st.top().first;
                        yy=st.top().second;
                        v.push_back(xx);
                        v.push_back(yy);
                        st.pop();
                    }while(xx!=x and yy!=it);
                    sort(v.begin(),v.end());
                    v.erase(unique(v.begin(),v.end()),v.end());
                    comp_bic.push_back(v);
                    v.clear();
                }
            }
            else
                low[x]=min(low[x],dfn[it]);
        }
}
int main()
{
    int i,j;
    f>>n>>m;
    while(m--)
    {
        f>>i>>j;
        G[i].push_back(j);
        G[j].push_back(i);
    }
    fill(dfn+1,dfn+n+1,-1);
    fill(low+1,low+n+1,-1);
    DFS(1,-1);
    g<<comp_bic.size()<<'\n';
    for(const auto it:comp_bic)
    {
        for(const auto i:it) g<<i<<' ';
        g<<'\n';
    }

    return 0;
}