Cod sursa(job #2852782)

Utilizator pielevladutPiele Vladut Stefan pielevladut Data 19 februarie 2022 15:59:07
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 100000;
int N, M, cnt, timp;
int tin[NMAX + 5];
int low[NMAX + 5];
bool vizitat[NMAX + 5];
vector<int> compBiconexe[NMAX + 5];
vector<int> g[NMAX + 5];
stack<int> stk;

void dfs(int fiu, int tata)
{
    int copii_radacina = 0;
    vizitat[fiu] = true;
    low[fiu] = tin[fiu] = ++timp;
    stk.push(fiu);
    for(auto it : g[fiu])
    {
        if(it == tata)
        {
            continue;
        }
        if(vizitat[it] == true)
        {
            low[fiu] = min(low[fiu], tin[it]);
        }
        else
        {
            dfs(it, fiu);
            low[fiu] = min(low[fiu], low[it]);
            if(low[it] >= tin[fiu])
            {
                cnt++;
                while(stk.top() != it)
                {
                    compBiconexe[cnt].push_back(stk.top());
                    stk.pop();
                }
                compBiconexe[cnt].push_back(stk.top());
                stk.pop();
                compBiconexe[cnt].push_back(fiu);
            }
        }
    }
}

int main()
{
    fin >> N >> M;
    while(M--)
    {
        int u, v;
        fin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    fout << cnt << '\n';
    for(int i = 1; i <= cnt; i ++)
    {
        for(auto it : compBiconexe[i])
        {
            fout << it << ' ';
        }
        fout << '\n';
    }
    return 0;
}