Pagini recente » Cod sursa (job #3239330) | Cod sursa (job #3149021) | Cod sursa (job #252707) | Cod sursa (job #3146533) | Cod sursa (job #802378)
Cod sursa(job #802378)
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
//int e_014_dfs()
int main()
{
string in_file = "dfs.in";
string out_file = "dfs.out";
const int MAX_N = 100000;
int n;
int m;
vector<int> adj_lists[MAX_N + 1];
int component[MAX_N + 1];
ifstream ifs(in_file.c_str());
ifs>>n>>m;
//read the edges and fill the adjacency list
for (int e = 1; e <= m; e++)
{
int v1, v2;
ifs>>v1>>v2;
adj_lists[v1].push_back(v2);
adj_lists[v2].push_back(v1);
}
ifs.close();
for (int v = 1; v <= n; v++) component[v] = -1;
int last_component_val = 0;
queue<int> Q;
for (int v = 1; v <= n; v++)
{
if (component[v] == -1)
{
Q.push(v);
component[v] = (++last_component_val);
while ( !Q.empty() )
{
int u = Q.front();
Q.pop();
for (vector<int>::iterator it = adj_lists[u].begin(); it != adj_lists[u].end(); it++)
{
int s = *it;
if (component[s] == -1)//if not processed and not in queue
{
Q.push(s);
component[s] = last_component_val;
}
}
}
}
}
ofstream ofs(out_file.c_str());
ofs<<last_component_val;
ofs.close();
return 0;
}