Pagini recente » Istoria paginii utilizator/boutiquequorn | Cod sursa (job #960254) | Cod sursa (job #1061533) | Cod sursa (job #3172072) | Cod sursa (job #2356816)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
struct Node
{
bool isVisited;
vector<int> edges;
Node() :
isVisited(false),
edges()
{
}
};
void DFS(vector<Node> &nodes, int currentNode)
{
nodes[currentNode].isVisited = true;
for(size_t i = 0; i < nodes[currentNode].edges.size(); i++)
{
int v = nodes[currentNode].edges[i];
if(!nodes[v].isVisited)
{
DFS(nodes, v);
}
}
}
int main()
{
ifstream fin("dfs.in");
ofstream fout("dfs.out");
if(!fin.is_open() || !fout.is_open())
return 1;
vector<Node> nodes;
int n, m, c = 0;
fin >> n >> m;
for(int i = 0; i < n; i++)
nodes.push_back(Node());
for(int i = 0, x, y; i < m; i++)
{
fin >> x >> y;
nodes[x - 1].edges.push_back(y - 1);
nodes[y - 1].edges.push_back(x - 1);
}
for(int i = 0; i < n; i++)
{
if(!nodes[i].isVisited)
{
c++;
DFS(nodes, i);
}
}
fout << c;
fin.close();
fout.close();
return 0;
}