Pagini recente » Cod sursa (job #2372250) | Cod sursa (job #2447139) | Cod sursa (job #1705767) | Cod sursa (job #1426996) | Cod sursa (job #1201942)
#include <fstream>
#include <vector>
#include <bitset>
#define lmax 100005
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <int> vi[lmax],vo[lmax],ordine,comp[lmax];
bitset <lmax>ap;
int n,m,nrcomponente;
int grup[lmax];
inline void read()
{
int x,y;
f>>n>>m;
for (int i=1;i<=m;i++)
{
f>>x>>y;
vo[x].push_back(y);
vi[y].push_back(x);
}
}
inline void parcurgere1(int nod)
{
vector <int>:: iterator it;
ap[nod]=1;
for (it=vo[nod].begin();it<vo[nod].end();it++)
if (ap[*it]==0)
parcurgere1(*it);
ordine.push_back(nod);
}
inline void parcurgere2(int nod,int nr)
{
vector <int>::iterator it;
grup[nod]=nr;
for (it=vi[nod].begin();it<vi[nod].end();it++)
if (!grup[*it])
parcurgere2(*it,nr);
}
inline void solve()
{
for (int i=1;i<=n;i++)
if (!ap[i])
parcurgere1(i);
for (;ordine.size();ordine.pop_back())
if (!grup[ordine.back()])
{
nrcomponente++;
parcurgere2(ordine.back(),nrcomponente);
}
for (int i=1;i<=n;i++)
comp[grup[i]].push_back(i);
}
inline void write()
{
g<<nrcomponente<<'\n';
for (int i=1;i<=nrcomponente;i++)
{
for (int j=0;j<comp[i].size();j++)
g<<comp[i][j]<<" ";
g<<'\n';
}
}
int main()
{
read();
solve();
write();
f.close();
g.close();
}