Cod sursa(job #2722148)

Utilizator Iulia25Hosu Iulia Iulia25 Data 12 martie 2021 16:53:03
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 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, top, nr_ctc, cnt;
int id[N], l[N], s[N], ctc[N];
vector <int> c[N], v[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;
	int x, y;
	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;
}