Pagini recente » Cod sursa (job #2708728) | Cod sursa (job #833911) | Cod sursa (job #2791122) | Cod sursa (job #1122144) | Cod sursa (job #3273033)
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int n, m, nrc;
vector<bool> comp;
vector<bool> viz1;
vector<bool> viz2;
vector<vector<int>> g;
vector<vector<int>> gt;
vector<vector<int>> afis;
void dfs1(int nod) {
viz1[nod] = 1;
for (auto i : g[nod])
if (!viz1[i])
dfs1(i);
}
void dfs2(int nod) {
viz2[nod] = 1;
for (auto i : gt[nod])
if (!viz2[i])
dfs2(i);
}
int main() {
cin >> n >> m;
afis.resize(n + 1);
g.resize(n + 1);
gt.resize(n + 1);
comp.resize(n + 1);
viz1.resize(n + 1);
viz2.resize(n + 1);
for (int i = 1; i <= m; ++i) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
gt[b].push_back(a);
}
for (int i = 1; i <= n; ++i) {
if (!comp[i]) {
++nrc;
dfs1(i);
dfs2(i);
for (int j = 1; j <= n; ++j) {
if (viz1[j] && viz2[j]) {
comp[j] = 1;
afis[nrc].push_back(j);
}
viz1[j] = viz2[j] = 0;
}
}
}
cout << nrc << '\n';
for (int i = 1; i <= nrc; ++i) {
for (auto j : afis[i])
cout << j << ' ';
cout << '\n';
}
return 0;
}