Pagini recente » Monitorul de evaluare | Cod sursa (job #50445) | Cod sursa (job #1612645) | Cod sursa (job #2152045) | Cod sursa (job #2173945)
#include <bits/stdc++.h>
#define Nmax 100001
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
list <int> G[Nmax];
list <int> Gt[Nmax];
int n,m,N;
int v[Nmax];
bitset <Nmax> viz;
list <int> ctc[Nmax];
void DFS1(int x)
{
viz[x]=true;
for(const auto &it:G[x])
if(!viz[it]) DFS1(it);
v[++N]=x;
}
void DFS2(int x)
{
viz[x]=false;
ctc[N].push_back(x);
for(const auto &it:Gt[x])
if(viz[it]) DFS2(it);
}
int main()
{
int i,j;
f>>n>>m;
while(m--)
{
f>>i>>j;
G[i].push_back(j);
Gt[j].push_back(i);
}
for(i=1;i<=n;i++)
if(!viz[i]) DFS1(i);
N=0;
for(i=n;i;i--)
if(viz[v[i]])
{
++N;
DFS2(v[i]);
}
g<<N<<'\n';
for(i=1;i<=N;i++,g<<'\n')
for(const auto &it:ctc[i]) g<<it<<' ';
return 0;
}