Cod sursa(job #1497997)

Utilizator Julian.FMI Caluian Iulian Julian. Data 7 octombrie 2015 21:14:57
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stdlib.h>
#define nmax 100005

using namespace std;
vector <bool> viz(nmax,false);
long *g[nmax];
ifstream fin("dfs.in");
ofstream fout("dfs.out");

void dfs(long x)
{int i;
    viz[x]=1;
    for(i=1;i<=g[x][0];i++)
        if(!viz[g[x][i]])
        dfs(g[x][i]);

}


int main()
{int i,n,m;
    fin>>n>>m;
    for(i=1;i<=n;i++)
        {g[i]=(long*)realloc(g[i],sizeof(long));
        g[i][0]=0;}
long x,y;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        g[x][0]++;
        g[x]=(long*)realloc(g[x],(g[x][0]+1)*sizeof(long));
        g[x][g[x][0]]=y;
        g[y][0]++;
        g[y]=(long*)realloc(g[y],(g[y][0]+1)*sizeof(long));
        g[y][g[y][0]]=x;
    }
long nr=0;
    for(i=1;i<=n;i++)
        if(!viz[i])
    {dfs(i);nr++;}
    fout<<nr;
}