Pagini recente » Cod sursa (job #3359370) | Cod sursa (job #3359865)
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int main() {
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
cin.tie(0); cout.tie(0);
ios_base::sync_with_stdio(false);
int N, M;
cin >> N >> M;
vector<vector<int>>G(N + 3), Gt(N + 3);
vector<int>count(N + 3);
for(int i = 0; i < M; i++) {
int x, y; cin >> x >> y;
G[x].push_back(y);
Gt[y].push_back(x);
}
vector<int>v(N + 3);
vector<int>ord;
auto dfs = [&] (int nod, auto self) -> void{
v[nod] = 1;
for(auto i : G[nod]) {
if(!v[i]) {
self(i, self);
}
}
ord.push_back(nod);
};
for(int i = 1; i <= N; i++) {
if(!v[i]) {
dfs(i, dfs);
}
}
vector<int>v1(N + 3);
vector<vector<int>>ctc;
auto dfs1 = [&] (int nod, auto self, vector<int>&ans) -> void{
v1[nod] = 1;
ans.push_back(nod);
for(auto i : Gt[nod]) {
if(!v1[i]) {
self(i, self, ans);
}
}
};
reverse(ord.begin(), ord.end());
for(auto i : ord) {
if(!v1[i]) {
vector<int>ans;
dfs1(i, dfs1, ans);
ctc.push_back(ans);
}
}
cout << ctc.size() << '\n';
for(auto i : ctc) {
for(auto j : i) {
cout << j << ' ';
}
cout << '\n';
}
}