Cod sursa(job #2722191)

Utilizator Iulia25Hosu Iulia Iulia25 Data 12 martie 2021 17:22:31
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

ifstream cin ("biconex.in");
ofstream cout ("biconex.out");

const int N = 1e5 + 5;

int n, m, x, y, cnt, nrc, top;
int id[N], l[N], s[N];
vector <int> v[N], c[N];

void dfs(int nod) {
  id[nod] = l[nod] = ++cnt;
  s[++top] = nod;
  for (auto it : v[nod])  {
    if (!id[it])  {
      dfs(it);
      l[nod] = min(l[nod], l[it]);
      if (l[it] == id[nod])  {
        ++nrc;
        while (s[top] != it)  {
          c[nrc].push_back(s[top]);
          --top;
        }
        c[nrc].push_back(nod);
        c[nrc].push_back(it);
        --top;
      }
    }
    else  {
      l[nod] = min(l[nod], id[it]);
    }
  }
}

int main()  {
  cin >> n >> m;
  for (int i = 1; i <= m; ++i)  {
    cin >> x >> y;
    v[x].push_back(y);
    v[y].push_back(x);
  }
  for (int i = 1; i <= n; ++i)  {
    if (!id[i])
      dfs(i);
  }
  cout << nrc << '\n';
  for (int i = 1; i <= nrc; ++i)  {
    sort(c[i].begin(), c[i].end());
    for (auto it : c[i])
      cout << it << ' ';
    cout << '\n';
  }
	return 0;
}