Cod sursa(job #2153679)

Utilizator anisca22Ana Baltaretu anisca22 Data 6 martie 2018 13:32:49
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
#include <bits/stdc++.h>
#define NMAX 100005
#define pii pair <int, int>

using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");

int N, M;
int nivel[NMAX], jumpBack[NMAX];

vector < vector <int> > rsp;
vector <int> v[NMAX], sol;
stack <pii> 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()
{
    fin >> N >> M;
    for (int i = 1; i <= M; i++)
    {
        int x, y;
        fin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    DFS(1, 0);
    fout << rsp.size() << "\n";
    for (int i = 0; i < rsp.size(); i++)
    {
        for (int j = 0; j < rsp[i].size(); j++)
                fout << rsp[i][j] << " ";
        fout << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}