Pagini recente » Borderou de evaluare (job #3309497) | Cod sursa (job #3324643) | Cod sursa (job #304086) | Cod sursa (job #3347433) | Cod sursa (job #3335544)
#include <bits/stdc++.h>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n, m, x, y;
int ans = 0;
vector <int> v[100005], vt[100005];
vector <int> vis(100005, 0), vist(100005, 0);
vector <int> order;
vector <vector<int>> components;
void dfs1 (int k) {
vis[k] = 1;
for (auto x: v[k])
if (vis[x] == 0)
dfs1(x);
order.push_back (k);
}
void dfs2 (int k) {
vist[k] = 1;
for (auto x: vt[k])
if (vist[x] == 0)
dfs2(x);
components[ans].push_back (k);
}
int main()
{
f >> n >> m;
for (int i=1; i<=m; ++i) {
f >> x >> y;
v[x].push_back (y);
vt[y].push_back (x);
}
for (int i=1; i<=n; ++i)
if (vis[i] == 0)
dfs1 (i);
for (int i=order.size()-1; i>=0; --i)
if (vist [order[i]] == 0) {
components.push_back ({});
dfs2 (order[i]);
++ans;
}
g << ans << '\n';
for (int i=0; i<ans; ++i) {
for (int j=components[i].size()-1; j>=0; --j)
g << components[i][j] << ' ';
g << '\n';
}
return 0;
}