Pagini recente » Cod sursa (job #2364430) | Cod sursa (job #2160198) | Cod sursa (job #2090960) | Cod sursa (job #2801379) | Cod sursa (job #2790223)
//
// main.cpp
// Algoritmi aplicati pe grafuri
//
// Created by Mara Dascalu on 27/10/2021.
//
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
#include <map>
#include <list>
using namespace std;
ifstream input("dfs.in");
ofstream output("dfs.out");
class Graph
{
int nodes, edges;
map<int, list<int>> adj;
public:
map<int, bool> visited;
void set_no_nodes(int n) {nodes = n;}
int get_no_nodes() {return nodes;}
void set_no_edges(int n) {edges = n;}
int get_no_edges() {return edges;}
void addEdge (int a, int b)
{
adj[a].push_back(b);
adj[b].push_back(a);
}
void DFS(int node)
{
visited[node] = 1;
//output<<node<<" ";
list<int> :: iterator iter;
for (iter = adj[node].begin(); iter != adj[node].end(); iter++)
if( !visited[*iter])
DFS(*iter);
}
// void afis_adj(int node){
// list<int> :: iterator i;
// for(i = adj[node].begin(); i != adj[node].end(); i++)
// output<<*i<<" ";
// }
}g;
int main(int argc, const char * argv[]) {
int no_nodes, no_edges, n1, n2, cc=0;
input>>no_nodes>>no_edges;
for (int i = 0; i < no_edges; i++)
{
input>>n1>>n2;
g.addEdge(n1, n2);
}
for (int i = 1; i <= no_nodes; i++)
if (!g.visited[i])
{
cc++;
g.DFS(i);
}
output<<cc<<" ";
}