Cod sursa(job #3289867)

Utilizator Allie28Radu Alesia Allie28 Data 28 martie 2025 21:20:54
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.8 kb
#include <bits/stdc++.h>

#define ll long long

using namespace std;

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

const int LMAX = 100005;
const int INF = 0x3f3f3f3f;
const ll MOD = 1000000007;

vector<pair<int, int>> L[LMAX];
bool viz[LMAX];
vector<int> st, ans[LMAX];
int lowLink[LMAX], depth[LMAX], idx;
//lowLink[i] --> inaltimea cea mai mica la care ar putea ajunge nodul i

void dfs(int node) {
    viz[node] = 1;
    lowLink[node] = depth[node];
    st.push_back(node);
    for (auto vec : L[node]) {
        if (!viz[vec.first]) {
            depth[vec.first] = depth[node] + 1;
            dfs(vec.first);
            lowLink[node] = min(lowLink[node], lowLink[vec.first]);
            if (lowLink[vec.first] >= depth[node]) {
                while (!st.empty() && st.back() != vec.first) {
                    ans[idx].push_back(st.back());
                    st.pop_back();
                }
                st.pop_back();
                ans[idx].push_back(vec.first);
                ans[idx].push_back(node);
                idx++;
            }
        }
        else if (depth[vec.first] + 1 != depth[node]) { //nu e tata
            lowLink[node] = min(lowLink[node], depth[vec.first]);
        }
    }
}


int main() {
    int n, m, i;
    fin>>n>>m;
    for (i = 0; i < m; i++) {
      int x, y;
      fin>>x>>y;
      L[x].push_back({y, i});
      L[y].push_back({x, i});
    }

    for (i = 1; i <= n; i++) {
      //finding articulation points
      if (!viz[i]) {
        dfs(i);
      }
//      fout<<dp[i]<<" ";
    }

    fout<<idx<<"\n";
    for (i = 0; i < idx; i++) {
        for (int vec : ans[i]) {
            fout<<vec<<" ";
        }
        fout<<"\n";
    }



    fin.close();
    fout.close();
    return 0;
}