Cod sursa(job #3040035)

Utilizator vladth11Vlad Haivas vladth11 Data 29 martie 2023 11:30:24
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.95 kb
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;

const ll NMAX = 1000001;
const ll INF = (1LL << 60);
const ll nrbits = 17;
const ll MOD = 9973;

vector <vector <int> > comp;
int low[NMAX];
int lvl[NMAX];
vector <int> v[NMAX];
vector <int> stiva;
vector <int> noduri;
int pa[NMAX];

void DFS(int node){
    noduri.push_back(node);
    low[node] = 2e9;
    for(auto x : v[node]){
        if(lvl[x] == 0){
            lvl[x] = lvl[node] + 1;
            pa[x] = node;
            DFS(x);
            low[node] = min(low[node], low[x]);
        }else if(lvl[x] + 1 != lvl[node]){ /// doar lvl[x] < lvl[node]
            low[node] = min(low[node], lvl[x]);
        }
    }
    if(lvl[node] > 1 && low[node] >= lvl[node] - 1){
        vector <int> nou;
        nou.push_back(pa[node]);
        while(noduri.back() != node){
            nou.push_back(noduri.back());
            noduri.pop_back();
        }
        nou.push_back(node);
        noduri.pop_back();
        comp.push_back(nou);
    }
}

int main() {
//#ifdef HOME
    ifstream cin("biconex.in");
    ofstream cout("biconex.out");
//#endif // HOME
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m, i;
    cin >> n >> m;
    for(i = 1; i <= m; i++){
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(i = 1; i <= n; i++){
        if(!lvl[i]){
            lvl[i] = 1;
            DFS(i);
            if(noduri.size() > 1){
                comp.push_back(noduri);
            }
            noduri.clear();
        }
    }
    cout << comp.size() << "\n";
    for(auto x : comp){
        for(auto y : x){
            cout << y << " ";
        }
        cout << "\n";
    }
    return 0;
}