Cod sursa(job #1138545)

Utilizator andi12Draghici Andrei andi12 Data 10 martie 2014 10:52:21
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <cstdio>

using namespace std;
int lst[100001];
int vf[400001];
int urm[400001];
bool viz[100001];
int nr;
inline void ad(int x,int y)
{
    nr++;
    vf[nr]=y;
    urm[nr]=lst[x];
    lst[x]=nr;
}
inline void dfs(int x)
{
    int p=lst[x],y;
    viz[x]=1;
    while(p!=0)
    {
        y=vf[p];
        if(viz[y]==0)
            dfs(y);
        p=urm[p];
    }
}
int main()
{
    FILE *in,*out;
    in=fopen("dfs.in","r");
    out=fopen("dfs.out","w");
    int n,m,i,j,x,y,ras=0;
    fscanf(in,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(in,"%d%d",&x,&y);
        ad(x,y);
        ad(y,x);
    }
    for(i=1;i<=nr;i++)
    {
        if(lst[i]==0)
            ras++;
        if(lst[i]!=0 && viz[i]==0)
        {
            dfs(i);
            ras++;
        }
    }
    fprintf(out,"%d",ras);
    return 0;
}