Mai intai trebuie sa te autentifici.

Cod sursa(job #2576236)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 6 martie 2020 18:00:03
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int NMAX = 100000;

int N, M;

vector <int> g[NMAX + 5];

int d[NMAX + 5], low[NMAX + 5];
stack <int> st;

int nr;
vector <int> bix[NMAX + 5];

void dfs(int node, int dad)
{
    d[node] = low[node] = d[dad] + 1;
    st.push(node);

    for(auto it : g[node])
    {
        if(it == dad)
            continue;

        if(d[it])
        {
            low[node] = min(low[node], d[it]);
            continue;
        }

        dfs(it, node);
        low[node] = min(low[node], low[it]);

        if(d[node] <= low[it]) ///node punct de articulatie
        {
            nr++;

            int k;

            do
            {
                k = st.top();
                st.pop();
                bix[nr].push_back(k);
            }
            while(k != it);

            bix[nr].push_back(node);
        }
    }
}

int main()
{
    fin >> N >> M;

    for(int i = 1; i <= M; i++)
    {
        int x, y;
        fin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    for(int i = 1; i <= N; i++)
        if(!d[i])
            dfs(i, 0);

    fout << nr << '\n';

    for(int i = 1; i <= nr; i++)
    {
        for(auto it : bix[i])
            fout << it << ' ';
        fout << '\n';
    }

    return 0;
}