Pagini recente » Cod sursa (job #63602) | Cod sursa (job #1351304) | Cod sursa (job #531683) | Cod sursa (job #2506205) | Cod sursa (job #2228216)
#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(200000, nullptr);
static vector<bool> vis(200000, false);
void dfs(int start)
{
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);
}
}
int main()
{
ifstream in("dfs.in");
ofstream out("dfs.out");
int n, m;
in >> n >> m;
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 < m; ++i)
{
if (vis[i])
continue;
comp++;
dfs(i);
}
out << comp << "\n";
return 0;
}