Cod sursa(job #931117)

Utilizator xbogdanBogdan Boamfa xbogdan Data 27 martie 2013 23:45:48
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <fstream>
#include <cstdlib>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
struct nod {
    int nd;
    nod *next;
};
void read(nod **&a,int &n)
{
    int nr;
    in >> n >> nr;
    // Alocare matrice
    a = (nod**)calloc(n+1,sizeof(nod*));
    for (int i = 0; i < n+1; ++i)
        a[i] = 0;
    // Citire graf
    for(int i = 0; i < nr; ++i)
    {
        int x,y;
        in >> x >> y;
        nod *p = new nod;
        p->nd = y;
        p->next = a[x];
        a[x] = p;
    }
}
void print(nod **a,int n)
{
    for (int i = 1; i < n+1; ++i)
    {
        cout<<i<<" | ";
        while(a[i])
        {
            cout<<a[i]->nd<<" ";
            a[i] = a[i]->next;
        }
        cout<<"\n";
    }
}
void dfs(int sursa,nod **a,int n,int *&viz) 
{
    viz[sursa] = 1;
    while(a[sursa])
    {
        int c = a[sursa]->nd;
        if( !viz[c] ) 
            dfs(c,a,n,viz);
        a[sursa] = a[sursa]->next;
    }
}
int main()
{
    int n;
    nod **a;
    read(a,n);
    //print(a,n);
    
    int *viz = (int*)calloc(n+1,sizeof(int));
    int nr = 0;
    for(int i = 1; i < n+1; i++)
        if(!viz[i])
        {
            dfs(i,a,n,viz);
            nr++;
        }
    out<<nr;
    return 0;
}