Pagini recente » Cod sursa (job #1450864) | Cod sursa (job #2293089) | Cod sursa (job #2222025) | Cod sursa (job #671156) | Cod sursa (job #360098)
Cod sursa(job #360098)
// BFS
#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>>left>>right;
List[left].push_back(right);
}
};
bool * used;
int v[1000000];
int nr_v;
int nr_com_conex;
void BFS(int node)
{
nr_v=1;
v[1]=node;
used[node]=1;
++nr_com_conex;
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];
for (int i=1; i<=nodes; ++i)
used[i]=0;
BFS(1);
};
void print(const char * out_file)
{
fstream g(out_file, ios::out);
g<<nr_com_conex;
g.close();
}
int main()
{
read("dfs.in");
solve();
print("dfs.out");
return 0;
}