Cod sursa(job #236268)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 27 decembrie 2008 01:00:27
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include<stdio.h>
struct Nod {
    int x;
    Nod *next;
};
Nod *a[100010];
Nod *b[100105];
int afis[200005];
int viz[100005];
int n;
int nc;
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 (viz[it->x] == nc)
     if (!viz2[it ->x])
      tDF(it -> x);
}

int DF(int s)
{
    viz[s] = nc;
    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++)
     {
       nc++;
       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;
}