Pagini recente » Cod sursa (job #3289081) | Cod sursa (job #3258929) | Cod sursa (job #3284151) | Cod sursa (job #2707225) | Cod sursa (job #3285000)
#ifndef LOCAL
#pragma GCC optimize("O3")
// #pragma GCC target("avx2")
#endif
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
using ll = long long;
using ci = const int;
using cll = const long long;
using namespace std;
const int NMAX = 1e5 + 5;
/*******************************/
// INPUT / OUTPUT
#ifndef LOCAL
ifstream in("ctc.in");
ofstream out("ctc.out");
#define cin in
#define cout out
#endif
/*******************************/
/// GLOBAL DECLARATIONS
int N, M;
int cnt;
int vis[NMAX], col[NMAX];
vector <int> topo;
vector <int> adj[NMAX], inv[NMAX], ctcs[NMAX];
/*******************************/
/// FUNCTIONS
void ReadInput();
void Solution();
void Output();
/*******************************/
///-------------------------------------
inline void ReadInput()
{
cin >> N >> M;
int x, y;
for (int i = 0 ; i < M ; ++ i)
{
cin >> x >> y;
adj[x].push_back(y);
inv[y].push_back(x);
}
}
///-------------------------------------
inline void dfs1(int node)
{
if (vis[node]) return;
vis[node] = true;
for (auto u: adj[node])
dfs1(u);
topo.push_back(node);
}
///-------------------------------------
inline void dfs2(int node)
{
if (col[node]) return;
col[node] = cnt;
for (auto u: inv[node])
dfs2(u);
}
///-------------------------------------
inline void Solution()
{
for (int node = 1 ; node <= N ; ++ node)
dfs1(node);
reverse(topo.begin(), topo.end());
for (auto node: topo)
{
if (!col[node])
{
cnt ++;
dfs2(node);
}
}
for (int node = 1 ; node <= N ; ++ node)
ctcs[col[node]].push_back(node);
}
///-------------------------------------
inline void Output()
{
cout << cnt << "\n";
for (int i = 1 ; i <= cnt ; ++ i)
{
for (auto node: ctcs[i]) cout << node << " ";
cout << "\n";
}
}
///-------------------------------------
int main()
{
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#endif
ReadInput();
Solution();
Output();
return 0;
}