Cod sursa(job #2098150)

Utilizator IustinPetrariuIustinian Petrariu IustinPetrariu Data 2 ianuarie 2018 14:38:34
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <iostream>
#include <fstream>
#define nmax 100005
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int n,m,viz[nmax],cnt=0;

typedef struct nod
{
    int x;
    nod*urm;
};
nod*pnod[nmax];
void adauga(int x, nod*&pp)
{
    nod*q=new nod;
    q->x=x;
    q->urm=pp;
    pp=q;

}
void citire()
{

    fin>>n>>m;
    int i,x,y;
    for(int i =1 ;i <= m ; i++)
    {
        fin>>x>>y;
        adauga(y,pnod[x]);
        adauga(x,pnod[y]);
    }

}
void dfs(int node)
{
    nod*w;
    viz[node]=1;
    for(w=pnod[node];w!=NULL; w=w->urm)
    {
        int t;
        t=w->x;
        if(!viz[t]) dfs(t);
    }


}
int main()
{
   citire();
   for(int i =1; i <= n ; i ++)
     if(!viz[i])
   {
       cnt++;
       dfs(i);
   }
   fout<<cnt;
    return 0;
}