Cod sursa(job #1830910)

Utilizator AndreiD31Dragan Andrei AndreiD31 Data 17 decembrie 2016 11:30:01
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>

using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");

struct nod
{
    int inf;
    nod *urm;
}*v[100001];


void adaug(nod *&prim, int x)
{
    nod *nou;
    nou=new nod;

    nou->inf=x;
    nou->urm=NULL;
    if(prim==NULL)prim=nou;
    else
    {
        nou->urm=prim;
        prim=nou;
    }

}

int viz[100001];
void DF (int i)
{
    viz[i]=1;
    nod *p;

    for(p=v[i];p;p=p->urm)
    {
        if(viz[p->inf]==0)DF(p->inf);
    }

}

int n,m,i,x,y,nr;
int main()
{
f>>n>>m;
for(i=1;i<=m;i++)
{
    f>>x>>y;
    adaug(v[x],y);
    adaug(v[y],x);
}
nr=0;
  for(i=1;i<=n;i++)
  {
      if(viz[i]==0){DF(i);nr++;}
  }

    g<<nr;
    return 0;
}