Pagini recente » Cod sursa (job #1819157) | Cod sursa (job #952313) | Cod sursa (job #877708) | Cod sursa (job #610920) | Cod sursa (job #1001116)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int N,M;
const int maxN = 100010;
vector<int>adj[maxN];
int vis[maxN];
void dfs();
void dfs(int i);
int main()
{
fin>>N;
fin>>M;
for(int i=0; i<M; i++)
{
int source,dest;
fin>>source;
fin>>dest;
adj[source].push_back(dest);
adj[dest].push_back(source);
}
dfs();
return 0;
}
void dfs()
{
int nrConexe =0;
for(int i=1; i<=N; i++)
{
if(vis[i]==0)
{
dfs(i);
nrConexe++;
}
}
fout<<nrConexe<<'\n';
}
void dfs(int nod){
vis[nod]=1;
int nrNeigh = adj[nod].size();
for(int i=0;i<nrNeigh;i++){
if(vis[adj[nod][i]]==0){
dfs(adj[nod][i]);
}
}
}