Pagini recente » Cod sursa (job #3345544) | Cod sursa (job #3353013) | Cod sursa (job #3337489) | Cod sursa (job #3346963) | Cod sursa (job #3340871)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int NMAX = 1e5 + 1;
vector<int> G[NMAX], GT[NMAX], ctc[NMAX];
vector<int> order;
bool viz[NMAX];
int nr = 0;
int n, m;
void read()
{
f >> n >> m;
for (int i = 1; i <= m; i++)
{
int a, b;
f >> a >> b;
G[a].push_back(b);
GT[b].push_back(a);
}
}
void order_dfs(int node)
{
viz[node] = true;
for (int to : G[node])
if (!viz[to])
order_dfs(to);
order.push_back(node);
}
void CTC_dfs(int node)
{
viz[node] = true;
ctc[nr].push_back(node);
for (int to : GT[node])
if (!viz[to])
CTC_dfs(to);
}
void dfs_driver_order()
{
for (int i = 1; i <= n; i++)
if (!viz[i])
order_dfs(i);
}
void dfs_driver_CTC()
{
for (int i = 1; i <= n; i++)
viz[i] = 0;
for (int x = n - 1; x >= 0; x--)
{
int i = order[x];
if (!viz[i])
{
nr++;
CTC_dfs(i);
}
}
}
void afis()
{
g << nr << '\n';
for (int i = 1; i <= nr; i++)
{
for (int x : ctc[i])
g << x << ' ';
g << '\n';
}
}
int main()
{
read();
dfs_driver_order();
dfs_driver_CTC();
afis();
return 0;
}