I am learning to find connected components in an undirected graph using DFS. I wrote the following code. It prints all vertices in a connected component in a new line. I am getting the wrong answer for the following input.
Input
7
2 1
1 0
6 3
5 4
-1 -1
Expected Output
0 1 2
3 6
4 5
Actual Output
0
1
2
3
4
5
6
If I input the same edges but with u < v, it prints the correct answer.
Input 2
7
1 2
0 1
3 6
4 5
-1 -1
Output 2 (all edges inputted were same but output is different)
0 1 2
3 6
4 5
Code
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mxV 100
// adjacency list
vector<vector<int>> adj(mxV);
// visited boolean
vector<bool> vst(mxV, false);
void dfs(int at) {
vst[at] = true;
cout << at << " ";
vector<int> nb = adj[at];
for (auto next : nb)
if (!vst[next])
dfs(next);
}
void addEdge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(v);
}
int main() {
int x,y,v;
cin >> v;
while (1) {
cin >> x >> y;
// take input until -1 -1
if (x == -1 || y == -1) {
break;
}
addEdge(x,y);
}
for (int i=0; i<v; i++) {
vst[i] = false;
}
// iterate over all vertices and dfs for those not visited
for (int i=0; i<v; i++) {
if (!vst[i]) {
dfs(i);
cout << "\n";
}
}
return 0;
}
Kindly help.