Cod sursa(job #2722980)

Utilizator alisavaAlin Sava alisava Data 13 martie 2021 14:10:55
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector<int> v[100005], answer[100005];
bool viz[100005];
int h[100005];
int low[100005];
int st[100005], top;
int nrSol;
void DFS(int nod, int father)
{
    low[nod] = h[nod] = h[father] + 1;
    viz[nod] = true;
    st[++top] = nod;
    for(auto son: v[nod])
    {
        if(son == father)
            continue;
        if(viz[son])
        {

            low[nod] = min(low[nod], h[son]);
            continue;
        }
        DFS(son, nod);
        low[nod] = min(low[nod], low[son]);
        if(low[son] >= h[nod])
        {
            nrSol++;
            while (st[top + 1] != son)
            {
                answer[nrSol].push_back(st[top--]);
            }
            answer[nrSol].push_back(nod);

        }


    }


}


int main()
{
    int n, m, x, y;
    fin  >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i = 1; i <= n; i++)
        if(!viz[i])
            DFS(i, 0);
    fout << nrSol << "\n";
    for(int i = 1; i <= nrSol; i++)
    {
        for(auto x: answer[i])
            fout << x << " ";
        fout << "\n";

    }

    return 0;
}