Pagini recente » Cod sursa (job #1720004) | Cod sursa (job #1265043) | Statistici Parasca Marius (NoWay) | Cod sursa (job #2042298) | Cod sursa (job #2105809)
#include <fstream>
#define NMAX 1000
#define MMAX 5000
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
void citire();
void DFS1(int k);
void DFS2(int k);
void rulare();
int n, m, la[NMAX][NMAX], lat[NMAX][NMAX], postord[NMAX], ctc[NMAX], nctc;
bool vizitat[NMAX], scris[NMAX];
int main()
{
citire();
rulare();
return 0;
}
void citire()
{
int i, a, b;
fin >> n>> m;
for (i=1; i<=m; i++)
{
fin >> a>> b;
la[a][0]++;
la[a][la[a][0]]=b;
lat[b][0]++;
lat[b][lat[b][0]]=a;
}
}
void rulare()
{
int i, j;
for (i=1; i<=n; i++)
{
if (!vizitat[i]) DFS1(i);
}
for (i=n; i>=1; i--)
{
if (!scris[postord[i]])
{
nctc++;
DFS2(postord[i]);
}
}
fout << nctc<< '\n';
for (i=1; i<=nctc; i++)
{
for (j=1; j<=n; j++) if (ctc[j]==i) fout << j<< ' ';
fout << '\n';
}
}
void DFS1(int k)
{
int i;
vizitat[k]=1;
for (i=1; i<=la[k][0]; i++)
{
if (!vizitat[la[k][i]]) DFS1(la[k][i]);
}
postord[0]++;
postord[postord[0]]=k;
}
void DFS2(int k)
{
int i;
scris[k]=1;
ctc[k]=nctc;
for (i=1; i<=lat[k][0]; i++)
{
if (!scris[lat[k][i]]) DFS2(lat[k][i]);
}
}