Cod sursa(job #2737870)

Utilizator PetyAlexandru Peticaru Pety Data 5 aprilie 2021 11:33:16
Problema Componente biconexe Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <bits/stdc++.h>
#define ll long long
#define ld long double

using namespace std;

const ll MOD = 1e9 + 7;
const ll INF = 1e9;

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

int n, m, back[100002], lvl[100002], viz[10002], nr;
stack<pair<int, int> >st;
vector<int>comp[100002], G[100002];

void dfs (int x, int p) {
  viz[x] = 1;
  lvl[x] = lvl[p] + 1;
  back[x] = lvl[x];
  for (auto it : G[x]) {
    if (!viz[it]) {   
      st.push({x, it});      
      dfs(it, x);
      if (back[it] >= lvl[x]) {
        nr++;
        while (st.top() != make_pair(x, it)) {
          comp[nr].push_back(st.top().first);
          comp[nr].push_back(st.top().second);
          st.pop();
        }
        comp[nr].push_back(x);
        comp[nr].push_back(it);
        st.pop();
      }
      back[x] = min(back[it], back[x]);
    }
    else {
      back[x] = min(back[x], lvl[it]);
    }
  }
}

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);
  }
  dfs(1, 0);
  fout << nr << "\n";
  for (int i = 1; i <= nr; i++) {
    sort(comp[i].begin(), comp[i].end());
    for (int j = 0; j < comp[i].size(); j++)
      if (!j || comp[i][j] != comp[i][j - 1])
        fout << comp[i][j] << " ";
    fout << "\n";
  }
  return 0;
}