Pagini recente » Cod sursa (job #347330) | Cod sursa (job #2410372) | Cod sursa (job #1310967) | Cod sursa (job #2529138) | Cod sursa (job #1464325)
#include <iostream>
#include <vector>
#include <fstream>
#include <string.h>
#define nmax 100005
using namespace std;
vector<int> G[nmax];
int T[nmax], viz[nmax], head, n, m, x, y, comps;
void build(){
ifstream f("dfs.in");
f >> n >> m;
for(int i=1; i<=m; i++){
f >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
}
void bfs(int start){
int i, j;
head = 1;
viz[start] = 1;
T[head] = start;
for(i = 1; i <= head; i++)
for(j = 0; j < G[T[i]].size(); j++){
if(!viz[G[T[i]][j]]){
T[++head] = G[T[i]][j];
viz[G[T[i]][j]] = 1;
}
}
}
int main()
{
ofstream g("dfs.out");
build();
memset(T, 0, sizeof(T));
for(int i=1; i<=n; i++)
if(!viz[i]){
comps++;
bfs(i);
}
g << comps;
return 0;
}