Pagini recente » Cod sursa (job #2922921) | Cod sursa (job #2514043) | Cod sursa (job #2507222) | Cod sursa (job #3032179) | Cod sursa (job #2671945)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
const int N_MAX = 1e5 + 1;
vector <int> graph[N_MAX];
stack <int> stk;
vector <bool> visited;
int edgesAdded = 0;
int unvisitedNodes;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
void DFS(int node)
{
int head = stk.top();
for(auto neighbor: graph[head])
{
if(visited[neighbor] == true)
{
continue;
}
stk.push(neighbor);
visited[neighbor] = true;
DFS(neighbor);
}
stk.pop();
}
int main()
{
int n, m, x;
fin >> n >> m;
visited.resize(n + 1);
fill(visited.begin(), visited.end(), false);
for(int i = 0, st, dr; i < m; i++)
{
fin >> st >> dr;
graph[st].push_back(dr);
graph[dr].push_back(st);
}
for(int i = 1; i <= n; i++)
{
if(visited[i] == true)
continue;
edgesAdded++;
visited[i] = true;
stk.push(i);
DFS(i);
}
fout << edgesAdded;
return 0;
}