Pagini recente » Cod sursa (job #862570) | Cod sursa (job #224027) | Cod sursa (job #214867) | Cod sursa (job #2422489) | Cod sursa (job #1168097)
#include <cstdlib>
#include <fstream>
#include <vector>
using namespace std;
void dfs(int node, vector< vector<int> > &neighbors, vector<int> &visited)
{
visited[node] = 1;
for (vector<int>::iterator it = neighbors[node].begin(); it != neighbors[node].end(); it++)
{
if (!visited[*it]) dfs(*it, neighbors, visited);
}
}
int main()
{
vector< vector<int> > neighbors;
vector<int> visited;
int M, N, a, b;
int componentCount;
fstream f, g;
f.open("dfs.in", ios::in);
g.open("dfs.out", ios::out);
f >> N >> M;
neighbors.resize(N);
visited.resize(N, 0);
for (int i = 0; i < M; i++)
{
f >> a >> b;
a--; b--;
neighbors[a].push_back(b);
neighbors[b].push_back(a);
}
componentCount = 0;
for (int i = 0; i< N; i++)
{
if (!visited[i])
{
componentCount++;
dfs(i, neighbors, visited);
}
}
g << componentCount;
f.close();
g.close();
return 0;
}