Pagini recente » Cod sursa (job #1368391) | Cod sursa (job #1446982) | Cod sursa (job #67782) | Cod sursa (job #2859687) | Cod sursa (job #1168107)
#include <cstdlib>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
void dfs(int node, const vector< vector<int> > &neighbors, vector<int> &visited)
{
stack<int> S;
int x;
S.push(node);
while(!S.empty())
{
x = S.top();
S.pop();
if (visited[x]) continue;
visited[x] = 1;
for (vector<int>::const_iterator it = neighbors[x].begin(); it != neighbors[x].end(); it++)
{
if (!visited[*it]) S.push(*it);
}
}
}
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;
}