Pagini recente » Cod sursa (job #1823162) | Rating Tudor Vioreanu (tudorDude) | Cod sursa (job #1890295) | Cod sursa (job #1866861) | Cod sursa (job #1639996)
#include <iostream>
#include <vector>
#include <stack>
#include <fstream>
using namespace std;
int n, m, i, x, y, nr = 0;
vector <vector <int> > graph;
vector <bool> viz;
ifstream f ("dfs.in");
ofstream g ("dfs.out");
void DFS (int vertex){
int i;
if (vertex < 0 || vertex > n-1) return;
stack <int> s;
int elem;
bool found;
s.push (vertex);
viz[vertex] = true;
//cout << "DFS: " << vertex << " ";
while (!s.empty()) {
elem = s.top();
found = false;
for (i = 0; i < graph[elem].size() && !found; i++)
if (!viz[graph[elem][i]]) found = true;
if (found) {
i--;
s.push (graph[elem][i]);
//cout << graph[elem][i] << " ";
viz [graph[elem][i]] = true;
}
else s.pop();
}
}
int main()
{
f >> n >> m;
graph.resize(n);
viz.resize(n, false);
for (i = 0; i < m; i++)
{
f >> x >> y;
x--; y--;
graph[x].push_back(y);
graph[y].push_back(x);
}
for (i = 0; i < n; i++)
if (!viz[i])
{
DFS(i);
nr++;
}
g << nr;
f.close();
g.close();
return 0;
}