Cod sursa(job #2136903)

Utilizator NannyiMaslinca Alecsandru Mihai Nannyi Data 20 februarie 2018 13:19:26
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.87 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
#define nmax 100005

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

struct str
{
    int nod1,nod2;
};

vector<int>Q[nmax],componentebiconexe[nmax];
vector<str>stk;

int n,m,low[nmax],lvl[nmax],tata[nmax],ncurent;

void read()
{
    f>>n>>m;
    for (int i=1; i<=m; ++i)
    {
        int a,b;
        f>>a>>b;
        Q[a].push_back(b);
        Q[b].push_back(a);
    }
}

void afis(int nodd1,int nodd2)
{
    while (stk.back().nod1!=nodd1||stk.back().nod2!=nodd2)
    {
        componentebiconexe[ncurent].push_back(stk.back().nod1);
        componentebiconexe[ncurent].push_back(stk.back().nod2);
        stk.pop_back();
    }
    componentebiconexe[ncurent].push_back(stk.back().nod1);
    componentebiconexe[ncurent].push_back(stk.back().nod2);
    stk.pop_back();
    ++ncurent;
}

void dfs(int nod)
{
    for (auto w:Q[nod])
    {
        if (tata[nod]==w)
            continue;
        if (lvl[w]==-1)
        {
            stk.push_back({nod,w});
            low[w]=lvl[w]=lvl[nod]+1;
            dfs(w);
            low[nod]=min(low[nod],low[w]);
            if (low[w]>=lvl[nod])
                afis(nod,w);
        }
        else
            low[nod]=min(low[nod],lvl[w]);
    }
}

void solve()
{
    for (int i=1; i<=n; ++i)
        lvl[i]=-1;
    tata[1]=-1;
    dfs(1);
    g<<ncurent<<'\n';
    for (int i=0; i<ncurent; ++i)
    {
        int last=-1;
        sort(componentebiconexe[i].begin(),componentebiconexe[i].end());
        for (auto w:componentebiconexe[i])
        {
            if (w==last)
                continue;
            else
            {
                g<<w<<' ';
                last=w;
            }
        }
        g<<'\n';
    }
}


int main()
{
    read();
    solve();
    return 0;
}