Pagini recente » Cod sursa (job #3210914) | Cod sursa (job #864554) | Cod sursa (job #1284708) | Cod sursa (job #171341) | Cod sursa (job #1104734)
#include <iostream>
#include <fstream>
using namespace std;
#define LE 1000
ifstream f("dfs.in");
ofstream g("dfs.out");
int lista_noduri[LE];
int muchii[LE][LE];
int inundat[LE];
int n,t,nr;
void BFS(int nod_start)
{
nr=0;
++nr;
lista_noduri[nr]=nod_start;// bag nodul de start in lista de noduri proaspat inundate
int j;
for(j=1;j<=nr;++j) /// forul asta e mai tricky umpic vezi restul algoritmului daca nu intalegi cum merge
{
int Nod=lista_noduri[j]; /// asta este nodul proaspat inundat la care trebe sa i inund posibili vecini neinundati
for(t=1;t<=n;++t) ///parcurg toate nodurile
if (muchii[Nod][t]==1)/// daca am muchie de la nodul Nod la nodul t inseamnda ca t e vecin cu Nod
if (inundat[t]==0) /// daca inundat[t] e 0 inseamna ca nu a fost inundat inainte , daca e 1 nu mai are rost sa il inund,pentru ca a fost inundat deja
{
inundat[t]=1;/// il marchez ca inundat
++nr;
lista_noduri[nr]=t; ///il bag in lista ca fiind un nod proaspat inundat
}
}
}
int main()
{
int i,n1,n2,m;
int nr_componente=0;
f>>n>>m;// n=numar noduri, m=numar muchii
for(i=1;i<=m;++i)///citesc muchiile
{
f>>n1>>n2;
muchii[n1][n2]=1;
muchii[n2][n1]=1;
}
for(i=1;i<=n;++i)
if (inundat[i]==0)
{
++nr_componente;
BFS(i);
}
g<<nr_componente<<'\n';
return 0;
}