Pagini recente » Cod sursa (job #2868634) | Cod sursa (job #2886072) | Cod sursa (job #2318210) | Cod sursa (job #3005646) | Cod sursa (job #2434546)
#include <fstream>
#include <vector>
using namespace std;
ifstream fi("ctc.in");
ofstream fo("ctc.out");
const int NMAX=1e5+5;
int n,m,x,y,viz1[NMAX],viz2[NMAX],ord[NMAX],nr,cnt;
vector <int> g[NMAX],invg[NMAX],comp[NMAX];
void dfs1(int x)
{
viz1[x]=1;
for(auto y:invg[x])
if(!viz1[y])
dfs1(y);
ord[++cnt]=x;
}
void dfs2(int x)
{
viz2[x]=nr;
comp[nr].push_back(x);
for(auto y:g[x])
if(!viz2[y]) dfs2(y);
}
int main()
{
fi>>n>>m;
for(int i=1;i<=m;i++)
{
fi>>x>>y;
g[x].push_back(y);
invg[y].push_back(x);
}
for(int i=1;i<=n;i++)
if(!viz1[i]) dfs1(i);
for(int i=n;i>=1;i--)
if(!viz2[ord[i]])
{
nr++;
dfs2(ord[i]);
}
fo<<nr<<"\n";
for(int i=1;i<=n;i++)
{
for(auto x:comp[i])
fo<<x<<" ";
fo<<"\n";
}
fi.close();
fo.close();
return 0;
}