Pagini recente » Cod sursa (job #133306) | Cod sursa (job #2544239) | Cod sursa (job #422279) | Cod sursa (job #657334) | Cod sursa (job #360099)
Cod sursa(job #360099)
// DFS
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
int nodes;
vector<vector<int> > List;
void read(const char * buff_file)
{
fstream f(buff_file, ios::in);
f>>nodes;
int edges;
f>>edges;
int left, right;
List.reserve(nodes+1);
List.resize(nodes+1);
for (int i=1; i<=nodes; ++i)
{
f>>left>>right;
List[left].push_back(right);
List[right].push_back(left);
}
f.close();
};
bool * used;
int v[100001];
int nr_v;
int nr_conex;
void BFS(int node)
{
++nr_conex;
nr_v=1;
v[1]=node;
used[node]=1;
for (int i=1; i<=nr_v; ++i)
{
for (vector<int>::iterator it=List[v[i]].begin(); it != List[v[i]].end(); it++)
if (used[*it]==0)
{
v[++nr_v]=*it;
used[*it]=1;
}
}
for (int i=1; i<=nodes; ++i)
if (used[i]==0)
BFS(i);
}
void solve()
{
used=new bool[nodes+1];
BFS(1);
};
void print(const char * out_file)
{
fstream g(out_file, ios::out);
g<<nr_conex;
g.close();
}
int main()
{
read("dfs.in");
solve();
print("dfs.out");
return 0;
}