Cod sursa(job #1110566)

Utilizator WarynaBotoaca Marina Waryna Data 18 februarie 2014 10:48:25
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include<fstream>
using namespace std;
struct nod
{
    int v;
    nod *urm;
};
nod *LA[100002];
int n,S;
void citire(int &n , nod *LA[])
{
    fstream fin;
    nod *p;
    int m,i,vf1,vf2;
    fin.open("dfs.in",ios::in);
    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 componente_conexe(int n, nod *LA[])
{
    fstream fout;
    int viz[100002],i,nrc;
    for(i=1;i<=n;i++)
    {
        viz[i]=0;
    }
    nrc=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);
    componente_conexe(n,LA);
    return 0;
}