Cod sursa(job #2199013)

Utilizator Anastasia11Susciuc Anastasia Anastasia11 Data 26 aprilie 2018 11:40:54
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include <bits/stdc++.h>
#define Nmax 100005

using namespace std;

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

int n, m;
int nivel[Nmax], jumpBack[Nmax];

vector < vector <int> > rsp;
vector <int> v[Nmax], sol;
stack <pair <int, int > > st;

void getComponent(int nod, int nxt)
{
    int x, y;
    do{
        x = st.top().first;
        y = st.top().second;
        st.pop();
        sol.push_back(x);
        sol.push_back(y);
    }while(nod != x || nxt != y);

    sort(sol.begin(), sol.end());
    sol.erase(unique(sol.begin(), sol.end()), sol.end());
    rsp.push_back(sol);
    sol.clear();
}

void DFS(int nod, int father)
{
    nivel[nod] = nivel[father] + 1;
    jumpBack[nod] = nivel[nod];

    vector <int> :: iterator it;
    for (it = v[nod].begin(); it != v[nod].end(); it++)
    {
        int nxt = *it;
        if (nxt == father) continue;
        if (!nivel[nxt])
        {
            st.push({nod, nxt});
            DFS(nxt, nod);
            jumpBack[nod] = min(jumpBack[nod], jumpBack[nxt]);
            if (jumpBack[nxt] >= nivel[nod])
                getComponent(nod, nxt);
        }
        else jumpBack[nod] = min(jumpBack[nod], nivel[nxt]);
    }
}

int main()
{
    f >> n >> m;
    for ( int i = 1 ; i <= m ; i ++ )
    {
        int x, y;
        f >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    DFS(1, 0);
    g << rsp.size() << "\n";
    for ( int i = 0 ; i < rsp.size() ; i ++ )
    {
        for ( int j = 0 ; j < rsp[i].size() ; j ++ )
                g << rsp[i][j] << " ";
        g << "\n";
    }
    f.close();
    g.close();
    return 0;
}