Cod sursa(job #2884311)

Utilizator Iulia14iulia slanina Iulia14 Data 2 aprilie 2022 20:46:24
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;
vector <int> g[N];
int n, m;
int low[N], lvl[N];
int k, st[N];
vector <int> comp[N];
int nr;
void dfs(int nod, int dad)
{
    lvl[nod] = low[nod] = lvl[dad] + 1;
    st[++k] = nod;
    for (auto son : g[nod])
    {
        if (son == dad)
            continue;
        if (lvl[son]) ///am mai fost
        {
            low[nod] = min(low[nod], lvl[son]);
            continue;
        }
        dfs(son, nod);
        if (low[son] >= lvl[nod])///daca din son nu se merge mai sus de nod
        {
            nr++;
            while (true)
            {
                comp[nr].push_back(st[k]);
                if (st[k] == son)
                    break;
                k--;
            }
            k--;
            comp[nr].push_back(nod);
        }
        else
            low[nod] = min(low[nod], low[son]);
    }
}
int v[N];
int main()
{
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1, 0);
    cout << nr << '\n';
    for (int i = 1; i <= nr; i++)
    {
        int mm = 0;
        for (auto j : comp[i])
            v[++mm] = j;
        sort(v + 1, v + mm + 1);
        for (int j = 1; j <= mm; j++)
            cout << v[j] << " ";
        cout << '\n';
    }
    return 0;
}