Pagini recente » Rezultatele filtrării | Cod sursa (job #2693074) | Borderou de evaluare (job #243376) | Rezultatele filtrării | Cod sursa (job #2722148)
#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;
}