Cod sursa(job #260197)

Utilizator c_e_manuEmanuel Cinca c_e_manu Data 16 februarie 2009 19:33:56
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include<fstream>
#include<algorithm>

using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

typedef struct nod{
        int info;
        nod *urm;
        } *pNod;
pNod v[100005];
int i,n,x,y,m,k,viz[100005];

void adauga(pNod &b, int c)
{       pNod p;
        p=new nod;
        p->info=c;
        p->urm=b;
        b=p;
}
        
void dfs(int x)
{       pNod p;
        viz[x]=1;
        for(p=v[x];p!=NULL;p=p->urm)
                if(!viz[p->info])
                        dfs(p->info);
}

int main()
{       fin>>n>>m;
        for(i=1;i<=m;i++)
        {       fin>>x>>y;
                adauga(v[x],y);
                adauga(v[y],x);
        }
        for(i=1;i<=n;i++)
                        if(!viz[i]) {k++;dfs(i);}
        fout<<k<<'\n';
        return 0;
}