DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
Experiment 7 (A)
Student Name: Mrigaank Jaswal UID: 22BCS14681
Branch: BE-CSE Section/Group: KRG_IOT-2B
Semester: 5 Date of Performance:4-10-24
Subject Name: AP Lab Subject Code: 22CSH-311
1. TITLE: Journey to the Moon
2. AIM:
The member states of the UN are planning to send 2 people to the moon. They
want them to be from different countries. You will be given a list of pairs of
astronaut ID's. Each pair is made of astronauts from the same country.
Determine how many pairs of astronauts from different countries they can
choose from.
3. Objective :
Print Complete the journeyToMoon function in the editor below.
4. Algorithm :
1. Initialize graph and read the number of vertices and edges.
2. Populate the adjacency list by reading edge connections.
3. Perform DFS to find all connected components and count their sizes.
4. Calculate the total number of ways to choose 2 vertices from all
nodes.
5. Subtract the ways of choosing 2 vertices from the same component to
get the result.
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
6. Implemetation/Code
#include <bits/stdc++.h>
#define MAX 643000
using namespace std;
vector<int> adj[MAX];
int visited[MAX], vertices;
void DFS(int u) {
visited[u] = 1; // Mark current vertex as visited
vertices++; // Count the number of vertices in this component
for (int v : adj[u]) {
if (!visited[v]) {
DFS(v); // Recursively visit all unvisited neighbors
}
}
}
int main() {
int n, m, u, v, numComponents = 0;
long long totalWays, sameWays = 0;
vector<int> eachC; // Stores the size of each connected component
cin >> n >> m;
if (n == 1) {
cout << "0\n";
return 0;
}
for (int i = 0; i < m; i++) {
cin >> u >> v;
adj[u].push_back(v); // Add edge u -> v
adj[v].push_back(u); // Add edge v -> u (since the graph is undirected)
}
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
for (int i = 0; i < n; i++) {
if (!visited[i]) { // If vertex i is not visited
vertices = 0; // Reset vertices count for the new component
DFS(i); // Explore this component
eachC.push_back(vertices); // Store the size of this component
numComponents++; // Increment component count
}
}
totalWays = n * (n - 1LL) / 2;
for (int i = 0; i < numComponents; i++) {
sameWays += (eachC[i] * (eachC[i] - 1LL)) / 2;
}
cout << totalWays - sameWays << "\n";
return 0;
}
Output
7. Time Complexity : O( n+m )
8. Space Complexity : O(n+m )
Learning Outcomes:-
1. Understanding DFS to explore all nodes in a connected component.
2. Learning how to represent a graph using an adjacency list.
3. Computing connected components in an undirected graph.
4. Calculating combinations of pairs using basic combinatorics.
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
Experiment 7 (B)
1. TITLE: Breadth First Search: Shortest Reach
2. AIM:
Consider an undirected graph where each edge weighs 6 units. Each of the nodes
is labelled consecutively from 1 to n. You will be given a number of queries. For
each query, you will be given a list of edges describing an undirected graph. After
you create a representation of the graph, you must determine and report the
shortest distance to each of the other nodes from a given starting position using
the breadthfirst search algorithm (BFS). Return an array of distances from the start
node in node number order. If a node is unreachable, return -1 for that node.
3. Objective
Complete the bfs function in the editor below. If a node is unreachable, distance is .
bfs has the following parameter(s):
• int n: the number of nodes
• int m: the number of edges
• int edges[m][2]: start and end nodes for edges
• int s: the node to start traversals from Returns
int[n-1]: the distances to nodes in increasing node number order, not including
start node (-1 if a node is not reachable)
4. Algorithm
1. Create an adjacency list from the input edges.
2. Initialize distances to all nodes as -1.
3. Use a queue to perform BFS starting from the given node.
4. Set the distance of the start node to 0.
5. For each node, visit its unvisited neighbors and update their distances.
6. Continue BFS until all reachable nodes are visited.
7. Exclude the start node from the result and return the distances.
5. Implemetation/Code
#include <bits/stdc++.h>
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
using namespace std;
const int MAXN = 1000;
int bfs(int n, int m, int edges[][2], int s, int *result) {
list<int> adj[MAXN];
for (int i = 0; i < m; ++i) {
adj[edges[i][0] - 1].push_back(edges[i][1] - 1);
adj[edges[i][1] - 1].push_back(edges[i][0] - 1);
}
int dists[MAXN];
fill(dists, dists + n, -1);
queue<int> q;
q.push(s - 1);
dists[s - 1] = 0;
while (!q.empty()) {
int node = q.front();
q.pop();
for (int child : adj[node]) {
if (dists[child] == -1) {
q.push(child);
dists[child] = dists[node] + 6;
}
}
}
int j = 0;
for (int i = 0; i < n; ++i) {
if (i != s - 1) {
result[j++] = dists[i];
}
}
return j;
}
int main() {
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
int edges[m][2];
for (int i = 0; i < m; ++i) {
cin >> edges[i][0] >> edges[i][1];
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
}
int s;
cin >> s;
int result[MAXN];
int result_size = bfs(n, m, edges, s, result);
for (int i = 0; i < result_size; i++) {
cout << result[i] << " ";
}
cout << endl;
}
return 0;
}
6.Output :
7.Time Complexity : O( n+m)
8. Space Complexity : O(n+m)
9. Learning Outcomes:-
1. Understand how BFS can be used to find shortest paths in an unweighted graph.
2. Learn how to implement an adjacency list using linked lists.
3. Handle multiple test cases efficiently with a queue-based approach.
DEPARTMENT OF
