Pagini recente » Cod sursa (job #755737) | Istoria paginii runda/cocalari_danseaza_2014/clasament | Cod sursa (job #2418714) | Cod sursa (job #2501976) | Cod sursa (job #2105812)
#include <fstream>
#include <vector>
#define nmax 100001
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int> lista[nmax];
vector<int> listaT[nmax];
int n,m,k,nr;
int postord[nmax];
bool ver[nmax];
int ctc[nmax];
void citire();
void DFS(int vf);
void DFST(int vf);
void afisare();
int main()
{int i;
citire();
for (i=1; i<=n; i++)
if (!ver[i])
DFS(i);
for (i=n; i>=1; i--)
{
if (ver[postord[i]])
{k++;
DFST(postord[i]);
}
}
afisare();
return 0;
}
void citire()
{
int i,j,x,y;
fin>>n>>m;
for (i=1; i<=m; i++)
{
fin>>x>>y;
lista[x].push_back(y);
listaT[y].push_back(x);
}
}
void DFS(int vf)
{int i;
ver[vf]=1;
for (i=0; i<lista[vf].size(); i++)
{
if (!ver[lista[vf][i]])
DFS(lista[vf][i]);
}
postord[++nr]=vf;
}
void DFST(int vf)
{
int i;
ver[vf]=0;
ctc[vf]=k;
for (i=0; i<listaT[vf].size(); i++)
{
if (ver[listaT[vf][i]])
DFST(listaT[vf][i]);
}
}
void afisare()
{int i,j;
fout<<k<<'\n';
for (i=1; i<=k; i++)
{for (j=1; j<=n; j++)
if (ctc[j]==i)
fout<<j<<' ';
fout<<'\n';
}
}