Pagini recente » Cod sursa (job #848768) | Cod sursa (job #2775652) | Cod sursa (job #1378846) | Cod sursa (job #2765830) | Cod sursa (job #2588445)
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
ifstream in ("dfs.in");
ofstream out ("dfs.out");
const int MAXN = 100001;
struct nod{
int val;
nod *next;
};
nod *lda[MAXN];
bool vz[MAXN];
void add(int x, int y)
{
nod *newnod = new nod;
newnod -> val = y;
newnod ->next = nullptr;
if (lda[x] == nullptr){
lda[x] = newnod;
return;
}
newnod -> next = lda[x];
lda[x] = newnod;
}
void DFS(int ind)
{
vz[ind] = 1;
//cout << ind << "\n";
for (nod *it = lda[ind]; it != nullptr; it = it ->next){
if (!vz[it ->val]){
DFS(it-> val);
}
}
}
int main()
{
int rs = 0;
int n;
in >> n;
int m;
in >> m;
for (;m--;){
int x,y;
in >> x >> y;
add(x,y);
add(y,x);
}
for (int i = 1; i <= n; i++){
if (!vz[i]){
rs++;
DFS(i);
}
}
out << rs << "\n";
return 0;
}