Cod sursa(job #2338171)

Utilizator andreigeorge08Sandu Ciorba andreigeorge08 Data 7 februarie 2019 09:40:25
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <bits/stdc++.h>

using namespace std;

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

vector <int> CompBicon[100005];
vector <int> L[100005];
int n, m, viz[100005], niv[100005], low[100005], nrComponente;
stack <int> st;

void DFS(int nod, int tata, int rad)
{
    viz[nod] = 1;
    niv[nod] = low[nod] = 1 + niv[tata];

    st.push(nod);

    for(auto fiu : L[nod])
        if(fiu != tata)
        {
            if(viz[fiu])
            {
                low[nod] = min(low[nod], low[fiu]);
                continue;
            }

            DFS(fiu, nod, rad);

            low[nod] = min(low[nod], low[fiu]);

            if(low[fiu] >= niv[nod])
            {
                nrComponente++;

                int x;

                do
                {
                    x = st.top();
                    st.pop();
                    CompBicon[nrComponente].push_back(x);
                }
                while(x != fiu);

                CompBicon[nrComponente].push_back(nod);
            }
        }
}

int main()
{
    int x, y;

    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        L[x].push_back(y);
        L[y].push_back(x);
    }

    for(int i = 1; i <= n; i++)
        if(!viz[i])
            DFS(i, 0, i);

    fout << nrComponente << "\n";
    for(int i = 1; i <= nrComponente; i++)
    {
        for(int j = 0; j < CompBicon[i].size(); j++)
            fout << CompBicon[i][j] << " ";
        fout << "\n";
    }
    return 0;
}