Cod sursa(job #2315112)

Utilizator andaraluca2001Anda Epure andaraluca2001 Data 9 ianuarie 2019 14:35:39
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <fstream>

using namespace std;
int n,m,v[100001],x,y,cnt;

ifstream in("dfs.in");
ofstream out("dfs.out");
typedef struct nod
{
    int info;
    nod *urm;
}*pnod;

pnod graf[100001];

void adauga(pnod &dest, int val)
{
    pnod p;
    p=new nod;
    p->info=val;
    p->urm=dest;
    dest=p;
}

void dfs(int nod)
{
    pnod p;
    v[nod]=1;
    for( p=graf[nod];p!=NULL;p=p->urm) if(!v[p->info]) dfs(p->info);
}
int main()
{
    in>>n>>m;

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

    for(int i=1;i<=n;i++)
    {
        if(!v[i])
        {
            cnt++;
            dfs(i);
        }
    }

    out<<cnt;
    return 0;
}