Pagini recente » Cod sursa (job #2871998) | Cod sursa (job #866297) | Cod sursa (job #2175999) | Cod sursa (job #1739663) | Cod sursa (job #3214776)
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
const int NMAX = 2e5 + 5;
int n, m;
vector<int> v[NMAX], inv[NMAX], top, culoare[NMAX];
bool viz[NMAX];
void dfs_top(int node)
{
viz[node] = true;
for(auto u : inv[node])
if(!viz[u])
dfs_top(u);
top.push_back(node);
}
void dfs(int node, int col)
{
culoare[col].push_back(node);
viz[node] = true;
for(auto u : v[node])
if(!viz[u])
dfs(u, col);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int a, b;
cin >> n >> m;
for(int i = 1; i <= m; i++)
{
cin >> a >> b;
v[a].push_back(b);
inv[b].push_back(a);
}
for(int i = 1; i <= n; i++)
if(!viz[i])
dfs_top(i);
int col = 0;
memset(viz, 0, sizeof(viz));
for(int i = top.size() - 1; i >= 0; i--)
{
if(!viz[top[i]])
{
col++;
dfs(top[i], col);
}
}
cout << col << "\n";
for(int i = 1; i <= col; i++)
{
for(auto u : culoare[i])
cout << u << " ";
cout << "\n";
}
}