Pagini recente » Cod sursa (job #2239698) | Cod sursa (job #2607381) | Cod sursa (job #2091832) | Cod sursa (job #903222) | Cod sursa (job #2789215)
#include<bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
#define cin fin
#define cout fout
#define N 100005
vector < vector < int > > g, gt, ans;
stack < int > s;
int n, m, x, y, f[N], vis[N], sol;
void df1(int x)
{
vis[x] = 1;
for(auto t : g[x])
{
int T = t;
if(vis[T] == 0)
{
df1(T);
}
}
s.push(x);
}
void df2(int x)
{
vis[x] = 0;
for(auto t : gt[x])
{
int T = t;
if(vis[T] == 1)
{
df2(T);
}
}
ans[sol].push_back(x);
f[x] = sol;
}
int main()
{
cin >> n >> m;
g.resize(n+5);
gt.resize(n+5);
ans.resize(n+5);
for(int i = 1 ; i <= m ; i++)
{
cin >> x >> y;
g[x].push_back(y);
gt[y].push_back(x);
}
for(int i = 1 ; i <= n ; i++)
{
if(vis[i] == 0)
{
df1(i);
}
}
while(!s.empty())
{
while(!s.empty() && vis[s.top()] == 0)
{
s.pop();
}
if(!s.empty())
{
sol++;
df2(s.top());
s.pop();
}
}
cout << sol << '\n';
for(int i = 1 ; i <= n ; i++)
{
if(f[i])
{
int nr = f[i];
sort(ans[nr].begin(),ans[nr].end());
cout << ans[nr].size() << " ";
for(auto t : ans[nr])
{
int T = t;
cout << T << " ";
f[T] = 0;
}
cout << '\n';
}
}
return 0;
}