BugCrush 2 Question 5 - BUGC205 - EDITORIAL
PROBLEM LINK
Author: codechefsrm
Editorialist : codechefsrm
DIFFICULTY
Hard
PREREQUISITES
Graph, Graph Traversal Algorithms
PROBLEM
Problem Description
Program to find the transpose of a graph.
Input:
No Input
Output:
0-> 2 ,1-> 0 4 ,2-> 3 ,3-> 0 4 ,4-> 0 ,
Rules:
Bugs will be mainly logical errors, syntax errors etc. They are specific to C++ language.
Since it is a debugging contest, you will be provided with a bugged solution below the Constraints section.
Please, see that you must adhere to the problem code provided, make changes only where necessary.
Participants can copy the code and compile it using an online compiler (Eg. CodeChef IDE).
Once the bugs are eliminated from the code, the clean code should be submitted by using the “Submit” button on the top-right corner.
Participants will be penalised for changing the entire problem solution or writing their own solution, completely different from the buggy code as provided in the
problem statement as our main intention is to test the debugging abilities of the participants.
Buggy Code in C++:
Please copy the following code and paste it into your compiler for debugging.
#include <bits/stdc++.h>
using namespace std;
void pusher(vector row[], int i, int slice)
{
row[i].push_back(slice);
}
void shift(vector col[], vector transpose[], int v)
{
for (int i = 0; i < v; i++)
for (int j = 0; j < col[i].size(); j--)
pusher(transpose, col[i][j], i);
}
void show(vector roll[], int k)
{
for (int i = 0; i < k; i++)
{
cout << i << "-> ";
for (int j = 0; j < roll[i].size; j++)
cout << roll[j][i] << " ";
cout << ",";
}
}
int main()
{
int v = 5;
vector<int> arr[v];
pusher(arr, 0, 1);
pusher(arr, 0, 4);
pusher(arr, 0, 3);
pusher(arr, 2, 0);
pusher(arr, 3, 2);
pusher(arr, 4, 1);
pusher(arr, 4, 3);
vector<int> change[v];
shift(arr, change, v);
show(change, v);
return 0;
}
SOLUTION
#include <bits/stdc++.h>
using namespace std;
void pusher(vector<int> row[], int i, int slice)
{
row[i].push_back(slice);
}
void shift(vector<int> col[], vector<int> transpose[], int v)
{
for (int i = 0; i < v; i++)
for (int j = 0; j < col[i].size(); j++)
pusher(transpose, col[i][j], i);
}
void show(vector<int> roll[], int k)
{
for (int i = 0; i < k; i++)
{
cout << i << "-> ";
for (int j = 0; j < roll[i].size(); j++)
cout << roll[i][j] << " ";
cout << ",";
}
}
int main()
{
int v = 5;
vector<int> arr[v];
pusher(arr, 0, 1);
pusher(arr, 0, 4);
pusher(arr, 0, 3);
pusher(arr, 2, 0);
pusher(arr, 3, 2);
pusher(arr, 4, 1);
pusher(arr, 4, 3);
vector<int> change[v];
shift(arr, change, v);
show(change, v);
return 0;
}
EXPLANATION
Transpose of a directed graph G is another directed graph on the same set of vertices with all of the edges reversed compared to the orientation of the corresponding
edges in G. That is, if G contains an edge (u, v) then the converse/transpose/reverse of G contains an edge (v, u) and vice versa.
We traverse the adjacency list and as we find a vertex v in the adjacency list of vertex u which indicates an edge from u to v in main graph, we just add an edge from v to u in the transpose graph i.e. add u in the adjacency list of vertex v of the new graph. Thus traversing lists of all vertices of main graph we can get the transpose graph. Thus the total time complexity of the algorithm is O(V+E) where V is number of vertices of graph and E is the number of edges of the graph.