Cod sursa(job #2722156)

Utilizator Iulia25Hosu Iulia Iulia25 Data 12 martie 2021 16:58:10
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

const int N = 1e5 + 5;

int n, m, x, y, top, cnt, nr_ctc;
int id[N], l[N], ctc[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);
    if (!ctc[it])
      l[nod] = min(l[nod], l[it]);
  }
  if (l[nod] == id[nod])  {
    ++nr_ctc;
    while (s[top + 1] != nod)  {
      ctc[s[top]] = nr_ctc;
      c[nr_ctc].push_back(s[top]);
      --top;
    }
  }
}

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