Pagini recente » Cod sursa (job #69429) | Cod sursa (job #2214046) | Cod sursa (job #873004) | Cod sursa (job #2924542) | Cod sursa (job #1110265)
#include <fstream>
#include <iostream>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int n,m;///numarul de noduri;
int viz[1066];/// vectorul de noduri vizate ( daca am mai fost in nodul V atunci viz[V]=1 , altfel viz[V]=0
int H[1066][1066];/// matricea de muchii H[i][j] este egal cu 1 daca am muchie intre i si j alfel e 0
int numar_comp; ///numarul de componente conexe (rezultatul)
void dfs(int X) ///sunt in nodul X cu dfs-ul
{
viz[X]=1; /// marchez Nodul X ca fiind vizat
int i;/// atentie i este declarat local adica in functie ,daca il declari global nu se revine bine din recursivitate
for(i=1;i<=n;++i)
if (H[X][i]==1) /// daca am muchie de la Nodul X la Nodul i
if (viz[i]==0) /// tot timpul ma duc intrun Nod care nu a mai fost vizat deja
{
dfs(i); /// ma mut cu dfs-ul in nodul i;
///dupa ce se apeleaza functia dfs(i) se revine recursiv in nodul X (seamana cu backtrackingu)
}
}
int main()
{
///citesc numarul de noduri, numarul de muchii si muchiile dintre ele , daca H[i][j] e 1 am muchie intre nodul i si j
f>>n>>m;
int i;
for(i=1;i<=m;++i)
{
int xx,yy;
f>>xx>>yy;
///graful e noerientat daca am muchie de la i la j am si de la j la i
H[xx][yy]=1;
H[yy][xx]=1;
}
for(i=1;i<=n;++i)
if (viz[i]==0) /// daca nodul i face dintro componenta conexa noua adica nu a mai fost vizat inainte
{
++numar_comp;
dfs(i);
}
g<<numar_comp<<'\n';
return 0;
}