Pagini recente » Cod sursa (job #963525) | Cod sursa (job #1878451) | Cod sursa (job #404738) | Cod sursa (job #263438) | Cod sursa (job #1783923)
#include <cstdio>
#include <deque>
#define NMAX 100005
using namespace std;
struct nod{
int x;
nod* next;
};
nod* g[NMAX];
bool vis[NMAX];
int n, m;
void add(int index, int val){
nod* nod_nou = new nod;
nod_nou->x=val;
nod_nou->next = g[index];
g[index] = nod_nou;
}
void dfs(int s){
deque<int> nodes;
nodes.push_back(s);
vis[s] = true;
while(!nodes.empty()){
int crt = nodes.front();
vis[crt] = true;
nodes.pop_front();
for(nod* ptr = g[crt]; ptr!=NULL;ptr=ptr->next){
if(!vis[ptr->x])nodes.push_back(ptr->x);
}
}
}
int main()
{
FILE* f=fopen("dfs.in", "r");
fscanf(f, "%d %d", &n, &m);
for(int i=0;i<m;i++){
int x, y;
fscanf(f, "%d %d", &x, &y);
add(x, y);
add(y, x);
}
fclose(f);
int comp=0;
for(int i=1;i<=n;i++){
if(!vis[i]){
dfs(i);
comp++;
}
}
f=fopen("dfs.out", "w");
fprintf(f, "%d", comp);
return 0;
}