Pagini recente » Cod sursa (job #869034) | Cod sursa (job #3238569) | Cod sursa (job #95558) | Cod sursa (job #2304994) | Cod sursa (job #360102)
Cod sursa(job #360102)
// 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);
int edges;
f>>nodes>>edges;
List.reserve(nodes+1);
List.resize(nodes+1);
int left, right;
for (int i=1; i<=edges; ++i)
{
f>>right>>left;
List[right].push_back(left);
List[left].push_back(right);
}
f.close();
};
bool used[200000];
int nr_conex;
void dfs(int i)
{
for (vector<int>::iterator it=List[i].begin(); it < List[i].end(); it++)
if (used[*it] == 0)
{
used[*it]=1;
dfs(*it);
}
};
void solve()
{
used[1]=1;
nr_conex=1;
dfs(1);
for (int i=1; i<=nodes; ++i)
if (used[i]==0)
{
++nr_conex;
used[i]=1;
dfs(i);
}
fstream g("dfs.out", ios::out);
g<<nr_conex;
g.close();
}
int main()
{
read("dfs.in");
solve();
return 0;
}