Pagini recente » Cod sursa (job #236720) | Cod sursa (job #1569422) | Istoria paginii runda/surprize_surprize/clasament | Cod sursa (job #907855) | Cod sursa (job #1783913)
#include <cstdio>
#include <deque>
#define NMAX 100000
using namespace std;
struct nod{
int x;
nod* next;
};
nod* g[NMAX];
bool vis[NMAX];
int n, m;
void add(int index, int val){
if(g[index]==NULL){
g[index] = new nod;
g[index]->x = val;
g[index]->next = NULL;
}
else{
nod* ptr = g[index];
while(ptr->next!=NULL)ptr = ptr->next;
ptr->next = new nod;
ptr = ptr->next;
ptr->x = val;
ptr->next = NULL;
}
}
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<n;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;
}