Pagini recente » Cod sursa (job #1656580) | Cod sursa (job #2040138) | Cod sursa (job #2059600) | Rating Balacescu Robert (Robert_24_52) | Cod sursa (job #2105817)
#include <cstdio>
#include <vector>
#define NMAX 100001
#define MMAX 5000
using namespace std;
FILE *fin=fopen("ctc.in", "r");
FILE *fout=fopen("ctc.out", "w");
void citire();
void DFS1(int k);
void DFS2(int k);
void rulare();
int n, m, postord[NMAX], ctc[NMAX], nctc;
vector <int> la[NMAX];
vector <int> lat[NMAX];
bool vizitat[NMAX], scris[NMAX];
int main()
{
citire();
rulare();
return 0;
}
void citire()
{
int i, a, b;
fscanf(fin, "%d %d", &n, &m);
for (i=1; i<=m; i++)
{
fscanf(fin, "%d %d", &a, &b);
la[a].push_back(b);
lat[b].push_back(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]);
}
}
fprintf(fout, "%d\n", nctc);
for (i=1; i<=nctc; i++)
{
for (j=1; j<=n; j++) if (ctc[j]==i) fprintf(fout, "%d ", j);
fprintf(fout, "\n");
}
}
void DFS1(int k)
{
int i;
vizitat[k]=1;
for (i=0; i<la[k].size(); 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=0; i<lat[k].size(); i++)
{
if (!scris[lat[k][i]]) DFS2(lat[k][i]);
}
}