Pagini recente » Cod sursa (job #809765) | Cod sursa (job #1552585) | Cod sursa (job #2726154) | Cod sursa (job #681498) | Cod sursa (job #2793153)
//
// main.cpp
// Algoritmi aplicati pe grafuri
//
// Created by Mara Dascalu on 27/10/2021.
//
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <bits/stdc++.h>
#include <map>
#include <list>
#include <set>
using namespace std;
ifstream input("dfs.in");
ofstream output("dfs.out");
class Graph
{
int nodes, edges;
vector<int> adj[100010] ;
bool visited[100010] = {0};
int cc = 0;
int cost[100010] = {0};
queue<int> queue_bfs;
int level[100010] = {0};
int low_level[100010] = {0};
stack<pair<int, int>> component_node;
vector<int> vec_scc[100010];
queue<int> queue_ts; //coada in care vom adauga doar nodurile care au gradul interior 0
int indegree[100010] ; //vectorul care retine gradul interior al fiecarui nod
vector<int> degree_seq; //vectorul care contine gradele unui posibil graf
public:
vector<int> bcc[100010]; //vectorul care stocheaza componentele biconexe
int current = 0;
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_dg ()
{
int no_nodes, no_edges;
input>>no_nodes>>no_edges;
set_no_nodes(no_nodes);
int node1, node2;
for(int i = 0 ; i < no_edges; i++)
{
input>>node1>>node2;
adj[node1].push_back(node2);
}
}
void addEdge_ug ()
{
int no_nodes, no_edges;
input>>no_nodes>>no_edges;
set_no_nodes(no_nodes);
int node1, node2;
for(int i = 0 ; i < no_edges; i++)
{
input>>node1>>node2;
adj[node1].push_back(node2);
adj[node2].push_back(node1);
}
}
void DFS(int node)
{
visited[node] = 1;
// output<<node<<" ";
for (int i = 0; i < adj[node].size(); i++)
if( !visited[adj[node][i]])
DFS(adj[node][i]);
}
// void afis_adj(int node){
// for (int i = 0; i < adj[node].size(); i++)
// cout<<adj[node][i]<<" ";
// }
int connectedComponents ()
{
for (int i = 1; i <= get_no_nodes(); i++)
if (!visited[i])
{
cc++;
DFS(i);
}
return cc;
}
}g;
int main(int argc, const char * argv[]) {
g.addEdge_ug();
output<<g.connectedComponents();
}