Pagini recente » Cod sursa (job #2934689) | Cod sursa (job #2061476) | Cod sursa (job #2758095) | Cod sursa (job #2678867) | Cod sursa (job #803265)
Cod sursa(job #803265)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
vector <int> lista[111111],listab[111111],a[111111];
bool marcat1[111111],marcat2[111111];
int time[111111],nr,k;
void dfs1(int poz)
{
int i;
for(i=0;i<lista[poz].size();++i)
{
if(!marcat1[lista[poz][i]])
{
marcat1[lista[poz][i]]=true;
dfs1(lista[poz][i]);
}
}
time[++nr]=poz;
}
void dfs2(int poz)
{
int i;
a[k].push_back(poz);
for(i=0;i<listab[poz].size();++i)
{
if(!marcat2[listab[poz][i]])
{
marcat2[listab[poz][i]]=true;
dfs2(listab[poz][i]);
}
}
}
int main()
{
int i,j,n,m,p,q;
in>>n>>m;
for(i=1;i<=m;++i)
{
in>>p>>q;
lista[p].push_back(q);
listab[q].push_back(p);
}
for(i=1;i<=n;++i)
{
if(!marcat1[i])
{
marcat1[i]=true;
dfs1(i);
}
}
for(i=n;i;--i)
{
if(!marcat2[time[i]])
{
marcat2[time[i]]=true;
++k;
dfs2(time[i]);
}
}
out<<k<<"\n";
for(i=1;i<=k;++i)
{
for(j=0;j<a[i].size();++j)
out<<a[i][j]<<" ";
out<<"\n";
}
return 0;
}