Cod sursa(job #1651734)

Utilizator robert.iacobIacob Robert robert.iacob Data 13 martie 2016 19:34:29
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include <fstream>
#define DimMax 100100

using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

struct Nod
{
    int info;
    Nod *leg;
};
Nod *L[DimMax];
int n,m;
int viz[DimMax];

void Inserare(int nod, int adiacent);
int Componente_Conexe(int noduri);
void Init_viz();
int DFS(int k);
void Citire();

void Citire()
{
    int x,y,i;
    fin>>n>>m;
    for(i=1;i<=n;i++)
        L[i]=NULL;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        Inserare(x,y);
        Inserare(y,x);
    }
}

void Inserare(int nod, int adiacent)
{
    Nod *p;
    p=new Nod;
    p->info=adiacent;
    p->leg=L[nod];
    L[nod]=p;
}

int Componente_Conexe(int noduri)
{
    int i,cnt=0;
    Init_viz();
    for(i=1;i<=noduri;i++)
        if(viz[i]==0)
        {
            DFS(i);
            cnt++;
        }
    return cnt;
}

int DFS(int k)
{
    Nod *p;
    int i;
    viz[k]=1;
    for(p=L[k];p!=NULL;p=p->leg)
        if(viz[p->info]==0)
            DFS(p->info);
}

void Init_viz()
{
    int i;
    for(i=1;i<=DimMax;i++)
        viz[i]==0;
}

int main()
{
    Citire();
    fout<<Componente_Conexe(n);
    return 0;
}