Cod sursa(job #1339721)

Utilizator eliseiDragoslav Elisei elisei Data 11 februarie 2015 08:26:58
Problema Parcurgere DFS - componente conexe Scor 65
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <fstream>
using namespace std;
int n,m;
struct Nod
{
  Nod * leg;
  int info;
};

Nod *L[100005];
int viz[100005];
void Adauga(int x, int y)
{
    Nod *q=new Nod;
    q->info=y;
    q->leg=L[x];
    L[x]=q;
}

void Citire()
{
    int x,y;
    ifstream fin("dfs.in");
    fin>>n>>m;
    for(int i=0;i<n;i++)
    {
        fin>>x>>y;
        Adauga(x,y);
        Adauga(y,x);
    }
    fin.close();
}

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

int main()
{
    Citire();
    int nr=0;
    for(int i=1;i<=n;i++)
        if(viz[i]==0)
        {
            DFS(i);
            nr++;
        }

    ofstream fout("dfs.out");
    fout<<nr<<"\n";
    fout.close();
    return 0;
}