Cod sursa(job #1856030)

Utilizator mihailarminia1234Arminia Mihail mihailarminia1234 Data 24 ianuarie 2017 14:17:56
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <bits/stdc++.h>

using namespace std;

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

struct Nod
{
    int info;
    Nod *next;
};

Nod *listaNoduri[100001], *lastNod[100001], *nou, *p;

int n,m,x,y,coada[100001],prim,ultim,nr;
bool viz[100001];

void AdaugaNod(int x,int y)
{
    if(listaNoduri[x]==NULL)
    {
        listaNoduri[x]=new Nod;
        listaNoduri[x]->info=y;
        listaNoduri[x]->next=NULL;
        lastNod[x]=listaNoduri[x];
    }
    else
    {
        nou=new Nod;
        nou->info=y;
        nou->next=NULL;
        lastNod[x]->next=nou;
        lastNod[x]=nou;
    }
}

void BFS(int nod)
{
    viz[nod]=true;
    prim=ultim=0;
    coada[prim]=nod;
    while(prim<=ultim)
    {
        for(p=listaNoduri[nod];p!=NULL;p=p->next)
            if(!viz[p->info])
            {
                ultim++;
                coada[ultim]=p->info;
                viz[p->info]=true;
            }
        prim++;
    }
}

int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y;
        AdaugaNod(x,y);
        AdaugaNod(y,x);
    }
    for(int i=1;i<=n;i++)
        if(!viz[i])
        {
            nr++;
            BFS(i);
        }
    g<<nr;
    return 0;
}