Cod sursa(job #3373923)

Utilizator elizageorgiana09Boros Eliza-Georgiana elizageorgiana09 Data 8 noiembrie 2026 10:58:28
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.98 kb
#include <bits/stdc++.h>
using namespace std;

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

int n, m, timp, cnt, top;

vector<int> h[100005];
vector<int> rez[100005];

int viz[100005], low[100005];
int stx[200005], sty[200005];
int folosit[100005];

void Componenta(int x,int y)
{
    cnt++; ///am gasit o noua comp biconexa

    int a,b;

    do
    {
        ///scot ultima muchie din stiva
        a=stx[top];
        b=sty[top];
        top--;

        ///adaug nodurile in comp
        if(folosit[a]!=cnt)
        {
            rez[cnt].push_back(a);
            folosit[a]=cnt;
        }

        if(folosit[b]!=cnt)
        {
            rez[cnt].push_back(b);
            folosit[b]=cnt;
        }

    }
    while(a!=x || b!=y);
}

void DFS(int nod,int tata)
{

    viz[nod]=low[nod]=++timp;

    for(int j:h[nod])
    {
        if(j==tata)
            continue;

        if(viz[j]==0)
        {

            stx[++top]=nod;
            sty[top]=j;

            DFS(j,nod);

            ///folosesc subarb fiului pt actualizare low
            low[nod]=min(low[nod],low[j]);


            ///daca din subarborele lui j nu pot ajunge la un stramos al unui nod -> comp
            if(low[j]>=viz[nod])
                Componenta(nod,j);
        }
        else if(viz[j]<viz[nod])
        {
            ///muchie de intoarcere catre un stramos
            stx[++top]=nod;
            sty[top]=j;

            low[nod]=min(low[nod],viz[j]);
        }
    }
}

int main()
{
    fin>>n>>m;

    for(int i=1; i<=m; i++)
    {
        int x,y;
        fin>>x>>y;

        h[x].push_back(y);
        h[y].push_back(x);
    }

    ///plec cu dfs din fiecare componenta conexa
    for(int i=1; i<=n; i++)
        if(viz[i]==0)
            DFS(i,0);

    fout<<cnt<<endl;

    for(int i=1; i<=cnt; i++)
    {
        for(int j:rez[i])
            fout<<j<<" ";

        fout<<endl;
    }

    return 0;
}