Pagini recente » Cod sursa (job #2712110) | Cod sursa (job #1118353) | Cod sursa (job #382122) | Cod sursa (job #2580263) | Cod sursa (job #3040231)
#include <bits/stdc++.h>
using namespace std;
ifstream in ("ctc.in");
ofstream out ("ctc.out");
const int NMAX = 1e5;
vector<int>g[NMAX + 5], rev[NMAX + 5];
bitset<NMAX + 5>vis;
vector<vector<int>>comp;
vector<int>ord, curr;
void dfs1 (int u)
{
vis[u] = true;
for (const auto &v : g[u])
{
if (!vis[v])
dfs1(v);
}
ord.push_back(u);
}
void dfs2 (int u)
{
vis[u] = true;
curr.push_back(u);
for (const auto &v : rev[u])
{
if (!vis[v])
dfs2(v);
}
}
int main()
{
int n, m;
in >> n >> m;
while (m--)
{
int u, v;
in >> u >> v;
g[u].push_back(v);
rev[v].push_back(u);
}
dfs1(1);
reverse(ord.begin(), ord.end());
vis = 0;
for (int i=1; i<=n; i++)
{
if (!vis[i])
{
curr.clear();
dfs2(i);
comp.push_back(curr);
}
}
out << (int) comp.size() << '\n';
for (auto &v : comp)
{
sort(v.begin(), v.end());
for (const auto &u : v)
out << u << ' ';
out << '\n';
}
return 0;
}