Cod sursa(job #1144467)

Utilizator andi12Draghici Andrei andi12 Data 17 martie 2014 10:00:00
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 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<=n;i++)
    {
        if(viz[i]==0)
        {
            dfs(i);
            ras++;
        }
    }
    fprintf(out,"%d",ras);
    return 0;
}