Cod sursa(job #1144465)

Utilizator andi12Draghici Andrei andi12 Data 17 martie 2014 09:58:19
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <cstdio>

using namespace std;
int v[1000001];
int lst[1000001];
int urm[1000001];
int bere[1000001];
int n,i,j,m,p,nr=0;
void ad(int x,int y)
{
    nr++;
    urm[nr]=v[x];
    v[x]=nr;
    lst[nr]=y;
}
void dfs(int x)
{
    int i,poz,p,y;
    p=v[x];
    if(bere[x]==0)
        bere[x]=2;
    while(p!=0)
    {
        y=lst[p];
        if(bere[y]==0)
            dfs(y);
        p=urm[p];
    }
}
int main()
{
    FILE *in,*out;
    in=fopen("berarii2.in","r");
    out=fopen("berarii2.out","w");
    fscanf(in,"%d%d%d",&n,&m,&p);
    int x,y,poz,ras=0;
    for(i=1;i<=m;i++)
    {
        fscanf(in,"%d%d",&x,&y);
        ad(y,x);
    }
    for(i=1;i<=p;i++)
    {
        fscanf(in,"%d",&x);
        bere[x]=1;
    }
    for(i=1;i<=n;i++)
    {
        if(bere[i]==1)
        {
            dfs(i);
        }
    }
    for(i=1;i<=n;i++)
    {
        if(bere[i]==0)
            ras++;
    }
    fprintf(out,"%d\n",ras);
    for(i=1;i<=n;i++)
    {
        if(bere[i]==0)
            fprintf(out,"%d\n",i);
    }
    return 0;
}