Pagini recente » Cod sursa (job #3289719) | Cod sursa (job #3294048) | Diferente pentru implica-te/arhiva-educationala intre reviziile 216 si 223 | Cod sursa (job #3293891) | Cod sursa (job #236261)
Cod sursa(job #236261)
#include<stdio.h>
struct Nod {
int x;
Nod *next;
};
Nod *a[100005];
Nod *b[100005];
int afis[100005];
int viz[100005];
int n;
int m;
int x;
int y;
int viz2[100005];
int nr;
int sir[100005];
void insert(Nod *&u, int val)
{
Nod *q = new Nod;
q -> x = val;
q -> next = u;
u = q;
}
int tDF(int s)
{
viz2[s] = 1;
afis[++afis[0]] = s;
for(Nod *it = b[s]; it; it = it -> next)
if (!viz2[it ->x])
tDF(it -> x);
sir[++sir[0]] = s;
}
int DF(int s)
{
viz[s] = 1;
for(Nod *it = a[s]; it; it = it -> next)
if (!viz[it ->x])
DF(it -> x);
sir[++sir[0]] = s;
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i = 1; i <= m; i++)
{
scanf("%d %d",&x,&y);
insert(a[x],y);
insert(b[y],x);
}
for(int i = 1; i <= n; i++)
{
if (!viz[i]) DF(i);
for(int j = sir[0]; j >= 1; j--)
if (!viz2[sir[j]])
{
tDF(sir[j]);
afis[++afis[0]] = 0;
nr++;
}
sir[0] = 0;
}
printf("%d\n",nr);
for(int i = 1; i <= afis[0]; i++)
if (afis[i] != 0) printf("%d ",afis[i]);
else printf("\n");
return 0;
}