Pagini recente » Cod sursa (job #786796) | Cod sursa (job #2091322) | Cod sursa (job #2660290) | Cod sursa (job #2464301) | Cod sursa (job #2228230)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
struct Node
{
int val;
Node* next;
Node( int val)
{
this->val = val;
next = nullptr;
}
};
static vector<Node*> v;
static vector<bool> vis;
void dfs(int start)
{
vis[start] = true;
if (v[start] == nullptr)
return;
stack<int> s;
s.push(start);
while (!s.empty())
{
int crt = s.top();
s.pop();
for (Node* node = v[crt]; node != nullptr; node = node->next)
if (!vis[node->val])
{
s.push(node->val);
vis[node->val] = true;
}
}
}
int main()
{
ifstream in("dfs.in");
ofstream out("dfs.out");
int n, m;
in >> n >> m;
v.resize(n + 1, nullptr);
vis.resize(n + 1, false);
for (int i = 0; i < m; ++i)
{
int u, w;
in >> u >> w;
if (u > w)
{
int aux = w;
w = u;
w = aux;
}
if (v[u] != nullptr)
{
v[u]->next = new Node( w );
}
else
{
v[u] = new Node( w );
}
if (v[w] != nullptr)
{
v[w]->next = new Node(u);
}
else
{
v[w] = new Node(u);
}
}
int comp = 0;
for (int i = 1; i <= n; ++i)
{
if (vis[i])
continue;
comp++;
dfs(i);
}
out << comp << "\n";
return 0;
}