Pagini recente » Cod sursa (job #3292382) | Diferente pentru implica-te/arhiva-educationala intre reviziile 196 si 223 | Cod sursa (job #3293630) | Autentificare | Cod sursa (job #236044)
Cod sursa(job #236044)
#include <cstdio>
const int maxn = 100001;
FILE *in = fopen("ctc.in", "r"), *out = fopen("ctc.out", "w");
struct graf
{
int nod;
graf *next;
};
int n, m;
graf *a[maxn], *at[maxn], *comp[maxn];
int viz[maxn], pord[maxn], k, nrc;
void add(int what, graf *&list)
{
graf *t = new graf;
t->nod = what;
t->next = list;
list = t;
}
void read()
{
fscanf(in, "%d %d", &n, &m);
int x, y;
for ( int i = 1; i <= m; ++i )
{
fscanf(in, "%d %d", &x, &y);
add(y, a[x]);
add(x, at[y]);
}
}
void df(int nod)
{
if ( viz[nod] )
return;
viz[nod] = 1;
graf *t = a[nod];
while ( t )
{
df(t->nod);
t = t->next;
}
pord[++k] = nod;
}
void dfT(int nod)
{
if ( !viz[nod] )
return;
viz[nod] = 0;
add(nod, comp[nrc]);
graf *t = at[nod];
while ( t )
{
dfT(t->nod);
t = t->next;
}
}
int main()
{
read();
for ( int i = 1; i <= n; ++i )
df(i);
for ( int i = n; i; --i )
if ( viz[ pord[i] ] )
{
++nrc;
dfT( pord[i] );
}
fprintf(out, "%d\n", nrc);
for ( int i = 1; i <= nrc; ++i )
{
graf *t = comp[i];
while ( t )
{
fprintf(out, "%d ", t->nod);
t = t->next;
}
fprintf(out, "\n");
}
return 0;
}