Pagini recente » Profil heman | Cod sursa (job #2793746) | Cod sursa (job #2632069) | Statistici Borz Denis (EzioAuditore) | Cod sursa (job #1463492)
#include <fstream>
using namespace std;
ifstream cin("dfs.in");
ofstream cout("dfs.out");
#define Nmax 100013
class cell {
public :
int node;
cell *prev;
cell (int a, cell *l) {node=a; prev=l;};
};
class UndirectedGraph {
private :
cell *adj[Nmax];
bool used[Nmax];
int dfs(int node){
used[node]=1;
for (cell *it = adj[node];it;it=it->prev)
if (!used[it->node])
dfs(it->node);
return 1;
}
public :
void addEdge(int a,int b){
cell *aux = new cell(b,adj[a]); adj[a]=aux;
aux = new cell(a,adj[b]); adj[b]=aux;
}
int conexCnt(int nodes){
int sol=0;
for (int i=1;i<=nodes;++i)
if (!used[i])
sol+=dfs(i);
return sol;
}
} Graph;
int n,m,a,b;
int main(void) {
cin>>n>>m;
while(m--) {
cin>>a>>b;
Graph.addEdge(a,b);
}
cout<<Graph.conexCnt(n);
return 0;
}