Cod sursa(job #2421046)

Utilizator raduandreiRadu Andrei raduandrei Data 13 mai 2019 23:28:46
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <bits/stdc++.h>
#define NMAX 100000
#define MMAX 200000
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
struct nod
{
    nod*urm;
    int info;
} *a[NMAX+1];
int n,m,v[NMAX+1],nrc;
void add(nod* &prim, int x)
{
    nod*p=new nod;
    p->info=x;
    p->urm=prim;
    prim=p;
}
void citire()
{
    fin>>n>>m;
    int x,y;
    for(int i=1; i<=m; ++i)
    {
        fin>>x>>y;
        add(a[x],y);
        add(a[y],x);
    }
}
void df(int x)
{
    v[x]=1;
    for(nod*q=a[x]; q; q=q->urm)
        if(v[q->info]==0)
        df(q->info);
}
int main()
{
    citire();
    for(int i=1; i<=n; ++i)
    if(!v[i])
    {
        nrc++;
        df(i);
    }
    fout<<nrc;
    return 0;
}