Cod sursa(job #1477456)

Utilizator andreiudilaUdila Andrei andreiudila Data 26 august 2015 12:49:09
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
typedef struct celula{
 int val;
 celula *next;

} *lista;
lista a;
lista graf[100001];
int n,m,i,j,x,y,viz[100001],nr;
void dfs(int nodc)
{
    lista i;
    viz[nodc]=1;
    for(i=graf[nodc];i!=NULL;i=i->next)
        {
            if(viz[i->val]==0)
            {
               // viz[i->val]=1
               dfs(i->val);
            }
        }
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        a= new celula;
        a->next=graf[x];
        a->val=y;
        graf[x]=a;

        a= new celula;
        a->next=graf[y];
        a->val=x;
        graf[y]=a;

    }
        for(i=1;i<=n;i++)
        {
            if(viz[i]==0)
            {
                nr++;
                dfs(i);
            }
        }
        fout<<nr;
    return 0;
}