Pagini recente » Cod sursa (job #1852091) | Cod sursa (job #1119428) | Cod sursa (job #3182776) | Cod sursa (job #2606891) | Cod sursa (job #2752530)
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define N 100001
#define M 200001
typedef struct element element;
struct element
{
int vf, urm;
};
element succesori[M], predecesori[M], ctc[N];
int stiva[N], vf, n, nrs, nrp, nrc, lst_s[N], lst_p[N], lst_c[N], nc;
bool viz[N];
void adauga_succesor(int x, int y)
{
///il adaug pe y in lista de succesori a lui x
++nrs;
succesori[nrs].vf = y;
succesori[nrs].urm = lst_s[x];
lst_s[x] = nrs;
}
void adauga_predecesor(int y, int x)
{
///il adauga pe x in lista de predecesori a lui y
++nrp;
predecesori[nrp].vf = x;
predecesori[nrp].urm = lst_p[y];
lst_p[y] = nrp;
}
void adauga_componenta(int nc, int x)
{
///il adaug pe x in lista de vf a ctc nc
++nrc;
ctc[nrc].vf = x;
ctc[nrc].urm = lst_c[nc];
lst_c[nc] = nrc;
}
void dfs(int x)
{
viz[x] = true;
int p = lst_s[x];
while (p != 0)
{
int y = succesori[p].vf;
if (!viz[y])
{
dfs(y);
}
p = succesori[p].urm;
}
stiva[++vf] = x;///x e adaugat in stiva cand m-am blocat in el
}
void dfs_t(int x)
{
viz[x] = true;
adauga_componenta(nc, x);///il adauga pe x in lista coresp. componentei nc
int p = lst_p[x];
while (p != 0)
{
int y = predecesori[p].vf;
if (!viz[y])
{
dfs_t(y);
}
p = predecesori[p].urm;
}
}
int main()
{
FILE *in, *out;
in = fopen("ctc.in", "r");
out = fopen("ctc.out", "w");
int m, i;
fscanf(in, "%d%d", &n, &m);
for (i = 0; i < m; i++)
{
int x, y;
fscanf(in, "%d%d", &x, &y);
adauga_succesor(x, y);
adauga_predecesor(y, x);
}
fclose(in);
///construiesc stiva -> sortare topologica
for (i = 1; i <= n; i++)
{
if (!viz[i])
{
dfs(i);
}
}
memset(viz, 0, N);
while (vf > 0)
{
int x = stiva[vf--];///am scos x din stiva
if (!viz[x])
{
++nc;
dfs_t(x);///viziteaza (folosind graful transpus) ctc a lui x
}
}
fprintf(out, "%d\n", nc);
for (i = 1; i <= nc; i++)
{
///afisez ctc i:
int p = lst_c[i];
while (p != 0)
{
int x = ctc[p].vf;
fprintf(out, "%d ", x);
p = ctc[p].urm;
}
fprintf(out, "\n");
}
fclose(out);
return 0;
}