Pagini recente » Cod sursa (job #1147237) | Cod sursa (job #3305683) | Cod sursa (job #849890) | Cod sursa (job #3337386) | Cod sursa (job #3333594)
#include <bits/stdc++.h>
using namespace std;
ifstream f ("ctc.in");
ofstream g ("ctc.out");
#define int long long
const int NMAX = 1e5 + 5;
int n, m;
vector <int> v[NMAX], t[NMAX];
vector <int> tout;
bitset <NMAX> visited;
vector<int> comp[NMAX];
int cnt;
void dfs2(int nod)
{
comp[cnt].push_back(nod);
visited[nod] = true;
for(auto & i : t[nod])
{
if(visited[i]) continue;
dfs2(i);
}
}
void dfs(int nod)
{
visited[nod] = true;
for(auto & i : v[nod])
{
if(visited[i]) continue;
dfs(i);
}
tout.push_back(nod);
}
int32_t main()
{
//ios_base :: sync_with_stdio(false);
//cin.tie(0);
f >> n >> m;
for(int i = 1; i <= m; i ++)
{
int x, y;
f >> x >> y;
v[x].push_back(y);
t[y].push_back(x);
}
for(int i = 1; i <= n; i ++)
{
if(visited[i] == false)
{
dfs(i);
}
}
reverse(tout.begin(), tout.end());
visited &= 0;
for(auto & i : tout)
{
if(visited[i] == false)
{
cnt ++;
dfs2(i);
}
}
g << cnt << '\n';
for(int i = 1; i <= cnt; i ++)
{
for(auto & j : comp[i])
{
g << j << " ";
}
g << '\n';
}
return 0;
}