Pagini recente » Cod sursa (job #1550723) | Cod sursa (job #3247505) | Cod sursa (job #2635307) | Cod sursa (job #2173118) | Cod sursa (job #3213908)
#include <bits/stdc++.h>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
#define pii pair<int, int>
#define pb push_back
#define fi first
#define se second
typedef long long ll;
const int NMAX = 1e5 + 30;
const int INF = 0x3f3f3f3f;
int n, m, x, y, v[NMAX], nrctc;
vector<vector<int>> graf(NMAX), gt(NMAX);
vector<int> fin;
vector<vector<int>> ctc(NMAX);
void read()
{
in >> n >> m;
for (int i = 1; i <= m; i++)
in >> x >> y, graf[x].pb(y), gt[y].pb(x);
}
void dfs(int node)
{
if (!nrctc)
{
v[node] = 1;
for (auto to : graf[node])
if (!v[to])
dfs(to);
fin.pb(node);
return;
}
// nrctc>=1
v[node] = 1;
ctc[nrctc].pb(node);
for (auto to : gt[node])
if (!v[to])
dfs(to);
}
void solve()
{
for (int i = 1; i <= n; i++)
if (!v[i])
dfs(i);
memset(v, 0, sizeof v);
reverse(fin.begin(), fin.end());
for (auto node : fin)
if (!v[node])
{
nrctc++;
dfs(node);
}
out << nrctc << '\n';
for (int i = 1; i <= nrctc; i++, out << '\n')
for (auto node : ctc[i])
out << node << ' ';
}
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
read();
solve();
return 0;
}