Pagini recente » Cod sursa (job #2092081) | Cod sursa (job #911001) | Cod sursa (job #2478138) | Cod sursa (job #621621) | Cod sursa (job #3273066)
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int n, m, nrc, i = 1, j = 1;
vector<int> viz1;
vector<int> viz2;
vector<vector<int>> g;
vector<vector<int>> gt;
vector<int> comp;
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;
if (viz1[nod] && viz2[nod]) {
comp[nod] = nrc;
afis[nrc].push_back(nod);
}
for (auto i : gt[nod])
if (!viz2[i])
dfs2(i);
}
int main() {
cin.tie(0);
cin.sync_with_stdio(false);
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);
while (m) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
gt[b].push_back(a);
--m;
}
while (i - 1 != n) {
if (!comp[i]) {
++nrc;
dfs1(i);
dfs2(i);
while (j - 1 != n) {
viz1[j] = viz2[j] = 0;
++j;
}
}
++i;
j = 0;
}
cout << nrc << '\n';
for (int i = 1; i <= nrc; ++i) {
for (auto j : afis[i])
cout << j << ' ';
cout << '\n';
}
return 0;
}