Pagini recente » Cod sursa (job #1724030) | Cod sursa (job #3138547) | Cod sursa (job #56597) | Cod sursa (job #1945648) | Cod sursa (job #1463997)
#include <iostream>
#include <vector>
#include <fstream>
#define nmax 10005
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<=n; i++){
f >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
}
void bfs(int start){
head = 1;
viz[start] = 1;
T[head] = start;
for(int i=1; i<=head; i++)
for(int j=0; j<G[T[i]].size(); j++)
if(!viz[G[T[i]][j]]){
T[++head] = G[T[i]][j];
viz[T[head]] = 1;
}
}
int main()
{
ofstream g("dfs.out");
build();
for(int i=1; i<=n; i++)
if(!viz[i]){
bfs(i);
comps++;
}
g << comps;
return 0;
}