Pagini recente » Cod sursa (job #2715423) | Cod sursa (job #896935) | Cod sursa (job #2637860) | Cod sursa (job #1734707) | Cod sursa (job #1808059)
//graf neorientat - sa se gaseasca numarul de componente conexe (DFS, alocare dinamica)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
int n,m;
int nrCompConexe;
struct nod{
int vecin;
struct nod *urm;
}*L[100002],*act;
bool viz[100002]; //vector noduri vizitate
void citeste()
{
int x,y;
in>>n>>m;
for(int i=1;i<=m;++i)
{
in>>x>>y;
//adauga nodul x la lista y
act=new nod;
act->vecin=x;
act->urm=L[y];
L[y]=act;
//adauga nodul y la lista x
act=new nod;
act->vecin=y;
act->urm=L[x];
L[x]=act;
}
}
void dfs(int nod)
{
struct nod *actual;
//marcheaza nodul ca vizitat
viz[nod]=1;
//ia toate muchiile nodului
actual=L[nod];
while(actual!=NULL)
{
//parcurge in adancime pentru primul vecin nevizitat
if(viz[actual->vecin]==0)
dfs(actual->vecin);
actual=actual->urm;
}
}
int main()
{
citeste();
/*
for(int i=1;i<=n;++i)
{
out<<i<<": ";
act=L[i];
while(act!=NULL)
out<<act->vecin<<" ", act=act->urm;
out<<"\n";
}
*/
//pentru a gasi numarul componentelor conexe
//ia fiecare nod pe rand, si aplica dfs
for(int i=1;i<=n;++i)
if(viz[i]==0)
++nrCompConexe, dfs(i);
//afiseaza numarul de componente conexe
out<<nrCompConexe<<"\n";
return 0;
}