Minimum Edge required to connect a unconnected directed graph

I am trying to write an algorithm that finds the minimum number of edges that are required to be added to connect all nodes from the starting vertices in a directed unconnected graph

#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
class Graph {
vector<vector<int>> vertices;
public:
Graph(int num_ver) {
vertices.resize(num_ver);
}
void addEdge(int ver1, int ver2) {
vertices[ver1].push_back(ver2);
}
vector<int>& getNeighbors(int ver) {
return vertices[ver];
}
int getVertices() {
return vertices.size();
}
};
void dfs(Graph& graph, int vertex, vector<bool>& visited) {
visited[vertex] = true;
vector<int>& neighbors = graph.getNeighbors(vertex);
for (int i = 0; i < neighbors.size(); i++) {
int n = neighbors[i];
if (!visited[n]) {
dfs(graph, n, visited);
}
}
}
int findMinEdges(Graph& graph) {
int num_vertices = graph.getVertices();
vector<bool> visited(num_vertices, false);
int edges = 0;
for (int i = 0; i < num_vertices; i++) {
if (!visited[i]) {
dfs(graph, i, visited);
edges++;
}
}
return (edges - 1);
}
int main() {
ifstream f("input.txt");
int vertices, edges, start;
f >> vertices >> edges >> start;
//cout << vertices << edges << start;'
Graph g(vertices + 1);
int v1, v2;
for (int i = 0; i < edges; i ++) {
f >> v1 >> v2;
g.addEdge(v1, v2);
}
f.close();
int min_edges = findMinEdges(g);
cout << "Minimum number of edges to make the graph connected: " << min_edges << endl;
ofstream o("output.txt");
o << min_edges;
o.close();
return 0;
}

The code uses a simple graph data structure and dfs algorithm to try to accomplish this. I have tried running the code on smaller inputs and it works but when the input size increases, it returns the wrong answer. I have tried using other algorithms i.e. Trajan's algorithm but even that has not worked for me.

A sample input file:

6 5 5
1 2
2 3
3 1
4 5
5 6

The first 3 numbers represent total vertices, total edges, starting vertex
and next line represent the edges (the first number is v1 and the second v2).

The code work fine for this but not for larger inputs. I dont seem to understand where the problem is!

https://file.io/bHnJHoqSE3ji contains the input text file. The output the algo is giving is 356 and the expected output is 263.

First, it seems that your adjacency list is 1-based while your visit
array is 0-based, and you sometimes use your adjacency list as if it's 0-based.

Second, I noticed that you didn't use the variable start at all. However, what if the graph looks like this:

2 <- 1

If the start node is 2, then the answer is 1. If the start node is 1 then the answer is 0. If you didn't use start in your code, it's impossible that your algorithm is correct.

As @TYeung points out, you have missed using the start vertex. You will get better result if you do start from the specified vertex:

int findMinEdges(Graph& graph, int start) {
int num_vertices = graph.getVertices();
vector<bool> visited(num_vertices, false);
dfs(graph, start, visited);
int edges = 0;
for (int i = 0; i < num_vertices; i++) {
if (!visited[i]) {
dfs(graph, i, visited);
edges++;
}
}
return (edges - 1);
}

However, whether or not you get the minimum number of edges depends on the order of the input vertices.

Consider this graph

0 -> 1
2 -> 1
3 -> 1
3 -> 2

Now input the vertices in a different order

0 -> 1
3 -> 1
3 -> 2
2 -> 1