Cod sursa(job #3139266)

Utilizator ioana.cCaprariu Ioana ioana.c Data 26 iunie 2023 19:15:51
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>
#define nmax 100010

using namespace std;

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

int n, m, vis[nmax], timer, tin[nmax], low[nmax];
vector <int> g[nmax];
stack <int> s;
vector <vector<int>> comp;

void dfs(int i, int p=-1){
    vis[i] = 1;
    timer++;
    tin[i] = timer; low[i] = timer;
    s.push(i);
    for(auto j:g[i]){
        if(j == -1)
            continue;
        if(vis[j])
            low[i] = min(low[i], tin[j]);
        else{
            dfs(j, i);
            low[i] = min(low[i], low[j]);
            if(low[j] >= tin[i]){
                comp.push_back({i, j});
                while(s.top() != j){
                    comp.back().push_back(s.top());
                    s.pop();
                }
                s.pop();
            }
        }
    }
}

int main()
{
    fin >> n >> m;
    for(int i=1; i<=m; i++){
        int x, y;
        fin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for(int i=1; i<=n; i++)
        if(!vis[i])
            dfs(i);
    fout << comp.size() << '\n';
    for(auto i:comp){
        for(auto j:i)
            fout << j << ' ';
        fout << '\n';
    }
    return 0;
}