Pagini recente » Cod sursa (job #1330380) | Cod sursa (job #99256) | Cod sursa (job #2873559) | Cod sursa (job #2111400) | Cod sursa (job #3125180)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
vector<int> graf[100005];
vector<int> grafinv[100005];
vector<int> s;
bool v[100005];
int v2[100005];
int id = 0;
void dfs(int now) {
v[now] = true;
for (int i : graf[now]) {
if (!v[i]) {
dfs(i);
}
}
s.push_back(now);
}
void dfs2(int now) {
v2[now] = id;
for (int i : grafinv[now]) {
if (!v2[i]) {
dfs2(i);
}
}
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
graf[x].push_back(y);
grafinv[y].push_back(x);
}
for (int i = 1; i <= n; i++) {
if (v[i]) continue;
dfs(i);
}
for (int i = s.size() - 1; i >= 0; i--) {
if (v2[s[i]] != 0) continue;
id++;
dfs2(s[i]);
}
vector<pair<int, int>> noduri;
for (int i = 1; i <= n; i++) {
noduri.push_back({ v2[i], i });
}
sort(noduri.begin(), noduri.end());
cout << id << '\n';
for (int i = 0; i < noduri.size(); i++) {
cout << noduri[i].second << ' ';
if (i + 1 < noduri.size() && noduri[i].first != noduri[i + 1].first) {
cout << '\n';
}
}
return 0;
}