Pagini recente » Cod sursa (job #1796379) | Cod sursa (job #620285) | Cod sursa (job #2187527) | Cod sursa (job #1258661) | Cod sursa (job #2090024)
#include <fstream>
#include <vector>
#include <queue>
#include <map>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int n, m;
vector<vector<int> > gr(100100);
vector<vector<int> > inv(100100);
vector<bool> used(100100);
vector<bool> USED(100100);
vector<vector<int> > ans;
queue<int> Q;
vector<int> verif;
map<int, bool> go;
vector<int> comp;
void BFS(int root) {
Q.push(root);
USED[root] = true;
comp.clear();
while (!Q.empty()) {
int now = Q.front();
Q.pop();
comp.push_back(now);
//cout<<now<<'\n';
for (auto &x : inv[now]) {
if ((!USED[x]) && go[x]) {
USED[x] = true;
Q.push(x);
}
}
}
ans.push_back(comp);
}
void bfs(int root) {
Q.push(root);
used[root] = true;
verif.clear();
go.clear();
while (!Q.empty()) {
int now = Q.front();
Q.pop();
go[now] = true;
verif.push_back(now);
//cout<<now<<'\n';
for (auto &x : gr[now]) {
if (!used[x]) {
used[x] = true;
Q.push(x);
}
}
}
for (auto &x : verif) {
if (!USED[x]) {
BFS(x);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
gr[a].push_back(b);
inv[b].push_back(a);
}
for (int i = 1; i <= n; i++) {
if (used[i]) {
continue;
}
bfs(i);
}
cout << ans.size() << '\n';
for (auto &x : ans) {
for (auto &y : x) {
cout << y << " ";
}
cout << '\n';
}
return 0;
}