Pagini recente » Cod sursa (job #2350043) | Cod sursa (job #911566) | Cod sursa (job #502744) | Cod sursa (job #2032382) | Cod sursa (job #632933)
Cod sursa(job #632933)
#define n_max 100001
#include <vector>
#include <stdio.h>
using namespace std;
int n,m;
vector <int> a[n_max];
int sel[n_max];
void dfs(int nod_sursa)
{
sel[nod_sursa]=1;
for( int i=0; i<a[nod_sursa].size(); i++)
// se parcurg vecinii nodului sursa. daca sunt neselectati devin, pe rand, noduri sursa la randul lor.
if (sel[a[nod_sursa][i]] == 0)
dfs(a[nod_sursa][i]);
}
int main()
{
int x,y;
int componente_conexe=0;
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
scanf("%d %d", &n,&m);
for(int i=1; i<=m; i++)
{
scanf("%d %d",&x,&y);
a[x].push_back(y);
a[y].push_back(x);
// se retin nodurile grafului neorientat dar pentru fiecare nod se retin si vecinii lui
}
for (int nod_sursa=1; nod_sursa<=n; nod_sursa++)
{
// se parcurg nodurile si se verifica daca sunt deja selectate
if (sel[nod_sursa] == 0)
{
componente_conexe++;
dfs(nod_sursa);
}
}
printf("%d",componente_conexe);
return 0;
}