Cod sursa(job #2262209)

Utilizator tifui.alexandruTifui Ioan Alexandru tifui.alexandru Data 17 octombrie 2018 08:44:50
Problema Componente biconexe Scor 42
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.73 kb
#include <bits/stdc++.h>
#define Nmax 100001
using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");

int N,M;
vector <int> G[Nmax],lvl,low,v;
vector <vector <int> > bic_comp;
stack <pair <int,int> > st;

void read()
{
    f>>N>>M;
    int x,y;
    while(M--)
    {
        f>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    lvl.resize(N+1);
    low.resize(N+1);
}

void DFS(int node, int parent)
{
    low[node]=lvl[node]=lvl[parent]+1;

    for(const auto &it:G[node])
        if(it!=parent)
        {
            if(!lvl[it])
            {
                st.push({node,it});
                DFS(it,node);
                low[node]=min(low[node],low[it]);

                if(low[it]>=lvl[node])
                {
                    v.clear();
                    int x,y;
                    do
                    {
                        x=st.top().first;
                        y=st.top().second;
                        st.pop();
                        v.push_back(x);
                        v.push_back(y);

                    }while(x!=node or y!=it);

                    bic_comp.push_back(v);
                }
            }
            else
                low[node]=min(low[node],low[it]);
        }
}

void print()
{
    g<<bic_comp.size()<<'\n';
    for(size_t i=0;i<bic_comp[i].size();++i)
    {
        sort(bic_comp[i].begin(),bic_comp[i].end());
        bic_comp[i].erase(unique(bic_comp[i].begin(),bic_comp[i].end()),bic_comp[i].end());
        for(size_t j=0;j<bic_comp[i].size();++j)
            g<<bic_comp[i][j]<<' ';
        g<<'\n';
    }
}

int main()
{
    read();
    DFS(1,0);
    print();

    return 0;
}