Cod sursa(job #3263867)

Utilizator Dragos__1_1Dragos Antohi Dragos__1_1 Data 16 decembrie 2024 17:45:46
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int t,n,i,j,m,a,b,timer,nr;
vector<int>adj[100005],comp[100005];
vector<int>stk,low(100005),def(100005);
void dfs (int node,int parent){
    low[node]=def[node]=++timer;
    stk.push_back(node);
    for (auto son:adj[node]){
        if(son==parent) continue;
        if(def[son]!=0){
            low[node]=min(low[node],def[son]);
        }
        else{
            dfs(son,node);
            low[node]=min(low[son],low[node]);
            if (low[son]>=def[node]){
                comp[++nr].push_back(node);
                while (comp[nr].back()!=son){
                    comp[nr].push_back(stk.back());
                    stk.pop_back();
                }
            }
        }
    }

}
int main()
{   f>>n>>m;
    for (i=1;i<=m;i++){
        f>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
        for (i=0;i<=n;i++)low[i]=def[i]=0;

    dfs(1,0);
    g<<nr<<'\n';
    for (i=1;i<=nr;i++){
        for (auto it:comp[i])
            g<<it<<' ';
        g<<'\n';
    }
    return 0;
}