Pagini recente » Cod sursa (job #2865570) | Cod sursa (job #1487135) | Cod sursa (job #1606402) | Cod sursa (job #667811) | Cod sursa (job #2228218)
#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)
{
stack<int> s;
s.push(start);
vis[start] = true;
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, nullptr);
vis.resize(n, false);
for (int i = 0; i < m; ++i)
{
int u, w;
in >> u >> w;
--u; --w;
if (v[u] != nullptr)
{
v[u]->next = new Node( w );
}
else
{
v[u] = new Node( w );
}
}
int comp = 0;
for (int i = 0; i < n; ++i)
{
if (vis[i])
continue;
comp++;
dfs(i);
}
out << comp << "\n";
return 0;
}