Cod sursa(job #2797567)

Utilizator Angel2IonitaAngel Ionita Angel2Ionita Data 10 noiembrie 2021 09:42:02
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <vector>
#include <fstream>
#include <queue>

using namespace std;

ifstream f("dfs.in");
ofstream o("dfs.out");

class Graph
{
    vector<bool> vis;
    vector<vector<int>> adjList;
    int size;

public:
    Graph(int n)
    {
        size = n + 1;
        adjList.resize(size);
        for (int i = 1; i <= size; i++)
            vis.push_back(false);
    }
    void addEdge(int start, int end)
    {
        adjList[start].push_back(end);
        adjList[end].push_back(start);
    }
    void DFS(int node)
    {
        vis[node] = true;
        for (auto i : adjList[node])
            if (!vis[i])
                DFS(i);
    }
    int Connected()
    {
        int k = 0;
        for (int i = 1; i <= size - 1; i++)
            if (!vis[i])
            {
                DFS(i);
                k++;
            }
        return k;
    }
};

int main()
{

    int n, m;
    int x, y;
    f >> n >> m;
    Graph g(n);
    for (int i = 1; i <= m; i++)
    {
        f >> x >> y;
        g.addEdge(x, y);
    }
    o<<g.Connected();
    return 0;
}