Cod sursa(job #3223768)

Utilizator Alex_DumitrascuAlex Dumitrascu Alex_Dumitrascu Data 13 aprilie 2024 16:05:49
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
vector <int> g[100005];
int level[100005];
int low[100005];
int used[100005];
bool articulatie[100005];
bool used_biconex[100005];
vector <int> sol[100005];
void dfs(int nod, int tata)
{
    int nrsons=0;
    used[nod]=1;
    level[nod]=level[tata]+1;
    low[nod]=level[nod];
    for (int vecin : g[nod]) {
        if (vecin==tata) continue;
        if (!used[vecin]) {
            nrsons++;
            dfs(vecin, nod);
            low[nod]=min(low[nod], low[vecin]);
        }
        else {
            low[nod]=min(low[nod], level[vecin]);
        }
        if (low[vecin]>=level[nod]) articulatie[nod]=1;
    }
    if (tata==0&&nrsons==1) articulatie[nod]=0;
    used[nod]=2;
}
void dfs_biconex(int nod, int index)
{
    used_biconex[nod]=1;
    sol[index].push_back(nod);
    for (int vecin : g[nod]) {
        if (articulatie[vecin]==1) {
            sol[index].push_back(vecin);
            used_biconex[vecin]=1;
        }
        if (used_biconex[vecin]) continue;
        dfs(vecin, index);
    }
}
int main()
{
    fin.tie(0); fin.sync_with_stdio(false);
    int n, m, a, b; fin>>n>>m;
    for (int i=1; i<=m; i++) {
        fin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for (int i=1; i<=n; i++) {
        low[i]=INT_MAX;
        level[i]=INT_MAX;
    }
    level[0]=-1;
    dfs(1, 0);
    int index=0;
    for (int i=1; i<=n; i++) {
        if (articulatie[i]==1) continue;
        if (!used_biconex[i]) {
            dfs_biconex(i, index);
            index++;
        }
    }
    fout<<index<<'\n';
    for (int i=0; i<index; i++) {
        for (int nod: sol[i]) {
            fout<<nod<<' ';
        }
        fout<<'\n';
    }
    return 0;
}