Cod sursa(job #2815043)

Utilizator IoanaLiviaPopescu15Ioana Livia IoanaLiviaPopescu15 Data 9 decembrie 2021 00:20:04
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define N 100001


using namespace std;

	
class Graph {
	
public:
	vector <int> adiacenta[N];
    bool visited[N];
    int n_g, m_g;
    vector <int> componente[N];
    vector <int> solution;
    void addEdge_neorientat(int h, int t);
    void addEdge_orientat(int h, int t);
    void BFS_mininum_distances(int root);
	void DFS(int vf);
    void SolveSortTop(int n_g, int m_g);
    void Assign(int u, int root, vector<int> &conexitate);
    void CTC();
    void Solve_Conexe_DFS();
};
	
 
	
void Graph::addEdge_neorientat(int h,int t)
{
     adiacenta[h].push_back(t);
     adiacenta[t].push_back(h);
}

void Graph::addEdge_orientat(int h,int t)
{
     adiacenta[h].push_back(t);
}
 
	
void Graph::DFS(int vf)
{
	visited[vf] = true;
	
	for(int i = 0; i < adiacenta[vf].size(); ++i)
		if (!visited[adiacenta[vf][i]])
			DFS(adiacenta[vf][i]);
    
    solution.push_back(vf);
	
}

void Graph::Solve_Conexe_DFS()
{
    ifstream fin("dfs.in");
    ofstream fout("dfs.out");

    int n, m, n1, n2, conexe = 0;

    fin>>n>>m;
    
    Graph g;

    for (int i = 1; i <= m; i++)
    {
        fin >> n1 >> n2;
        addEdge_neorientat(n1,n2);
    }

    for(int i = 1; i <= n; i++){
        if (!visited[i])
        {
           conexe += 1;
           DFS(i);
        }
    }

    fout << conexe;
}
int main()
{
    Graph g;
    g.Solve_Conexe_DFS();

    return 0;
}