Pagini recente » Cod sursa (job #2299584) | Cod sursa (job #1089486) | Cod sursa (job #2750405) | Cod sursa (job #2579464) | Cod sursa (job #2719603)
#include <iostream>
#include <fstream>
#include <forward_list>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,a,b,t,cnt;
bool viz1[100005],viz2[100005];
forward_list < int > v1[200005];
forward_list < int > v2[200005];
vector < int > v[100005];
stack < int > s;
void DFS1(int x)
{
viz1[x]=1;
for(auto it=v1[x].begin(); it!=v1[x].end();it++)
if(!viz1[*it])
DFS1(*it);
s.push(x);
}
void DFS2(int x)
{
viz2[x]=1;
v[cnt].push_back(x);
for(auto it=v2[x].begin(); it!=v2[x].end();it++)
if(!viz2[*it])
DFS2(*it);
}
int main()
{
fin >> n >> m;
for(;m;--m)
{
fin >> a >> b;
v1[a].push_front(b);
v2[b].push_front(a);
}
for(int i=1;i<=n;i++)
if(!viz1[i])
DFS1(i);
while(!s.empty())
{
t=s.top();
s.pop();
if(!viz2[t])
{
cnt++;
DFS2(t);
sort(v[cnt].begin(),v[cnt].end());
}
}
fout << cnt << '\n';
for(int i=1;i<=cnt;i++)
{
for(auto it=v[i].begin();it!=v[i].end();it++)
fout << *it << " ";
fout << '\n';
}
return 0;
}