Pagini recente » Cod sursa (job #2132309) | Cod sursa (job #1907821) | Cod sursa (job #1386787) | Cod sursa (job #972846) | Cod sursa (job #526890)
Cod sursa(job #526890)
#include<cstdio>
#include<queue>
using namespace std;
struct list {
int neigh;
list *next;
};
list *listad[100001];
bool viz[100001];
int N, M;
void readData() {
scanf("%d %d", &N, &M);
int x, y;
for (int i = 0; i < M; i++) {
scanf("%d %d ", &x, &y);
list *aux = new list;
aux->neigh = y;
aux->next = listad[x];
listad[x] = aux;
aux = new list;
aux->neigh = x;
aux->next = listad[y];
listad[y] = aux;
}
}
void bfs(int source){
queue<int> neigh;
viz[source] = 1;
neigh.push(source);
int current;
list *aux;
while (!neigh.empty()){
current = neigh.front();
neigh.pop();
aux = listad[current];
while (aux) {
if (!viz[aux->neigh]) {
viz[aux->neigh] = 1;
neigh.push(aux->neigh);
}
aux = aux->next;
}
}
}
int main() {
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
readData();
int compconex = 0;
for (int i = 1; i <= N; i++) {
if (!viz[i]) {
compconex++;
bfs(i);
}
}
printf("%d\n",compconex);
return 0;
}