Cod sursa(job #1110562)

Utilizator vladteodor97Cirstina Vlad vladteodor97 Data 18 februarie 2014 10:42:14
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include<fstream>
using namespace std;
struct nod{
    int v;
    nod* urm;
};
nod* LA[100002];
int n;
void citire(int &n,nod* LA[])
{
    fstream fin;
    fin.open("dfs.in",ios::in);
    int m,i,vf1,vf2;
    nod*p;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>vf1>>vf2;
        p=new nod;
        p->v=vf2;
        p->urm=LA[vf1];
        LA[vf1]=p;
        p=new nod;
        p->v=vf1;
        p->urm=LA[vf2];
        LA[vf2]=p;
    }
    fin.close();
}
void dfs(int vf ,int n,nod* LA[],int viz[])
{
    nod*p;
    viz[vf]=1;
    for(p=LA[vf];p!=0;p=p->urm)
    {
        if(viz[p->v]==0)
        {
            dfs(p->v,n,LA,viz);
        }
    }
}

void componenteconexe(int n,nod* LA[])
{
    fstream fout;
    int viz[100002],nrc,i;
    for(i=1;i<=n;i++)
    {
        viz[i]=0;
    }
    for(i=1;i<=n;i++)
    {
        if(viz[i]==0)
        {
            nrc++;
            dfs(i,n,LA,viz);
        }
    }
    fout.open("dfs.out",ios::out);
    fout<<nrc;
    fout.close();
}
int main()
{
    citire(n,LA);
    componenteconexe(n,LA);
    return 0;
}