Cod sursa(job #2220270)

Utilizator adimiclaus15Miclaus Adrian Stefan adimiclaus15 Data 11 iulie 2018 01:00:28
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int viz[100001],nr;
struct lista
{
    int nod;
    lista *urm;
};
lista *a[100001];
void adauga(int i,int j)
{
    lista *p;
    p=new lista;
    p->nod=j;
    p->urm=a[i];
    a[i]=p;
}
void dfs(int x)
{
    lista *p;
    viz[x]=1;
    for(p=a[x];p!=NULL;p=p->urm)
    {
        if(viz[p->nod]==0)
        {
            dfs(p->nod);
        }
    }
}
int main()
{
    int i,j,n,m;
    f>>n>>m;
    while(m--)
    {
        f>>i>>j;
        adauga(i,j);
        adauga(j,i);
    }
    for(i=1;i<=n;i++)
    {
        if(viz[i]==0)
        {
            nr++;
            dfs(i);
        }
    }
    g<<nr;
    return 0;
}