Pagini recente » Cod sursa (job #1953590) | Cod sursa (job #2485020) | Monitorul de evaluare | Cod sursa (job #1059132) | Cod sursa (job #1044785)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
struct node
{
vector<int> vecini;
bool vizitat = false;
};
void dfs(node* noduri, int i)
{
stack<node*> stiva;
stiva.push(&noduri[i]);
while (stiva.empty() == false)
{
node* top = stiva.top();
stiva.pop();
top->vizitat = true;
for (vector<int>::const_iterator it = top->vecini.begin(); it != top->vecini.end(); it++)
{
if (noduri[*it].vizitat == false)
stiva.push(&noduri[*it]);
}
}
}
int main()
{
ifstream IN("dfs.in");
ofstream OUT("dfs.out");
node *noduri;
int n, m;
int componenteCon = 0;
IN >> n >> m;
noduri = new node[n + 1];
for (int i = 0; i < m; i++)
{
int x, y; IN >> x >> y;
noduri[x].vecini.push_back(y);
noduri[y].vecini.push_back(x);
}
for (int i = 1; i <= n; i++)
{
if (noduri[i].vizitat == false)
dfs(noduri, i), ++componenteCon;
}
delete[] noduri;
OUT << componenteCon << "\n";
return 0;
}