Scribd
Upload
3 views9 pages

Graph - InClass, PostClass, Challenges Solution

The document contains several C programming problems related to graph theory, including constructing transport networks, social networks, and weighted graphs. It also includes algorithms for depth-first search (DFS) and breadth-first search (BFS) to explore connectivity and find shortest paths. Additionally, it addresses challenges like road network connectivity and edge removal for connected components.

Uploaded by

srinithirajesh1234
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views9 pages

Graph - InClass, PostClass, Challenges Solution

The document contains several C programming problems related to graph theory, including constructing transport networks, social networks, and weighted graphs. It also includes algorithms for depth-first search (DFS) and breadth-first search (BFS) to explore connectivity and find shortest paths. Additionally, it addresses challenges like road network connectivity and edge removal for connected components.

Uploaded by

srinithirajesh1234
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Graph – In Class, Post Class and Challenges Solution

In Class Problems
Problem 1: City Transport Network
#include <stdio.h>
int main() {
int n, m;
scanf("%d %d", &n, &m);
int adj[n][n];
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
adj[i][j] = 0;
}
}
int u, v;
for(int i = 0; i < m; i++) {
scanf("%d %d", &u, &v);
adj[u - 1][v - 1] = 1;
}

for(int i = 0; i < n; i++) {


for(int j = 0; j < n; j++) {
printf("%d ", adj[i][j]);
}
printf("\n");
}
return 0;
}

Problem 2 - Constructing a Social Network Graph


#include <stdio.h>
int main() {
int n, m;
scanf("%d %d", &n, &m);
int adj[n][n];
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
adj[i][j] = 0;
}
}
int u, v;

for(int i = 0; i < m; i++) {


scanf("%d %d", &u, &v);
adj[u - 1][v - 1] = 1;
adj[v - 1][u - 1] = 1; // undirected graph
}

for(int i = 0; i < n; i++) {


for(int j = 0; j < n; j++) {
printf("%d ", adj[i][j]);
}
printf("\n");
}
return 0;
}
Problem 3 - City Transportation System
#include <stdio.h>
int main() {
int n, m;
scanf("%d %d", &n, &m);
int adj[n][n];
int size[n];
for(int i = 0; i < n; i++) {
size[i] = 0;
}
int u, v;
for(int i = 0; i < m; i++) {
scanf("%d %d", &u, &v);

// Convert to 0-based indexing


u = u - 1;
v = v - 1;

// Add v to u's list


adj[u][size[u]] = v;
size[u]++;

// Add u to v's list (undirected graph)


adj[v][size[v]] = u;
size[v]++;
}
// Print adjacency list
for(int i = 0; i < n; i++) {
printf("City %d: ", i + 1);

for(int j = 0; j < size[i]; j++) {


printf("%d ", adj[i][j] + 1); // convert back to 1-based
}
printf("\n");
}
return 0;
}

Problem 4 - Constructing a Weighted Graph


#include <stdio.h>

int main() {
int n, m;
scanf("%d %d", &n, &m);

int adj[n][n]; // stores neighbors


int weight[n][n]; // stores weights
int size[n]; // number of neighbors

for(int i = 0; i < n; i++) {


size[i] = 0;
}
int u, v, w;

// Input edges
for(int i = 0; i < m; i++) {
scanf("%d %d %d", &u, &v, &w);

// Convert to 0-based
u = u - 1;
v = v - 1;
// Add edge u → v
adj[u][size[u]] = v;
weight[u][size[u]] = w;
size[u]++;

// Add edge v → u (undirected)


adj[v][size[v]] = u;
weight[v][size[v]] = w;
size[v]++;
}

// Print adjacency list


for(int i = 0; i < n; i++) {
printf("%d", i + 1);
for(int j = 0; j < size[i]; j++) {
printf(" -> (%d, %d)", adj[i][j] + 1, weight[i][j]);
}
printf("\n");
}
return 0;
}

Problem 5 - Exploring City Routes


#include <stdio.h>
#define MAX 100

int adj[MAX][MAX]; // adjacency list


int size[MAX]; // number of neighbors
int visited[MAX]; // visited array

// DFS function
void dfs(int node) {
printf("%d ", node);
visited[node] = 1;

for(int i = 0; i < size[node]; i++) {


int neighbor = adj[node][i];
if(visited[neighbor] == 0) {
dfs(neighbor);
}
}
}
int main() {
int n, m;
scanf("%d", &n);
scanf("%d", &m);

// Initialize
for(int i = 0; i < n; i++) {
size[i] = 0;
visited[i] = 0;
}

// Input edges
for(int i = 0; i < m; i++) {
int u, v;
scanf("%d %d", &u, &v);
adj[u][size[u]++] = v;
adj[v][size[v]++] = u; // undirected graph
}
int start;
scanf("%d", &start);
dfs(start);
return 0;
}

Problem 6 - City Infrastructure Planning


#include <stdio.h>
#include <stdbool.h>

int adj[100][100];
int size[100];

void bfs(int start, int n) {


bool visited[100] = {false};
int queue[100];
int front = 0;
int rear = 0;
visited[start] = true;
queue[rear++] = start;

while(front < rear) {


int district = queue[front++];
printf("%d ", district + 1);
for(int i = 0; i < size[district]; i++) {
int neighbor = adj[district][i];
if(!visited[neighbor]) {
visited[neighbor] = true;
queue[rear++] = neighbor;
}
}
}
}

int main() {
int n, m;
scanf("%d", &n);
scanf("%d", &m);
for(int i = 0; i < n; i++) {
size[i] = 0;
}
for(int i = 0; i < m; i++) {
int u, v;
scanf("%d %d", &u, &v);
u--;
v--;
adj[u][size[u]++] = v;
adj[v][size[v]++] = u;
}

int start;
scanf("%d", &start);
start--;
bfs(start, n);
return 0;
}
Post Class Problems
Problem 1 - Road Network Connectivity
#include <stdio.h>
#define MAX 100

int graph[MAX][MAX];
int reverseGraph[MAX][MAX];
int visited[MAX];
int n;

// DFS function
void dfs(int node, int arr[MAX][MAX]) {
visited[node] = 1;

for(int i = 1; i <= n; i++) {


if(arr[node][i] == 1 && !visited[i]) {
dfs(i, arr);
}
}
}
// Function to reset visited array
void resetVisited() {
for(int i = 1; i <= n; i++) {
visited[i] = 0;
}
}
int main() {
int m;
scanf("%d", &n);
scanf("%d", &m);

// Input edges
for(int i = 0; i < m; i++) {
int u, v;
scanf("%d %d", &u, &v);
graph[u][v] = 1;
// reverse graph
reverseGraph[v][u] = 1;
}
// DFS on original graph
dfs(1, graph);
for(int i = 1; i <= n; i++) {
if(!visited[i]) {
printf("The road network is not connected.");
return 0;
}
}
// Reset visited array
resetVisited();
// DFS on reversed graph
dfs(1, reverseGraph);

for(int i = 1; i <= n; i++) {


if(!visited[i]) {
printf("The road network is not connected.");
return 0;
}
}
printf("The road network is connected.");
return 0;
}
Problem 2 - Access to Libraries in HackerLand
#include <stdio.h>
#define MAX 100

int adj[MAX][MAX];
int size[MAX];
int visited[MAX];

// DFS function
int dfs(int node) {
visited[node] = 1;
int cities = 1;
for(int i = 0; i < size[node]; i++) {
int next = adj[node][i];
if(!visited[next]) {
cities += dfs(next);
}
}
return cities;
}

int main() {
int q;
scanf("%d", &q);
while(q--) {
int n, m;
int c_lib, c_road;
scanf("%d %d %d %d", &n, &m, &c_lib, &c_road);
// Reset arrays
for(int i = 1; i <= n; i++) {
size[i] = 0;
visited[i] = 0;
}
// Input roads
for(int i = 0; i < m; i++) {
int u, v;
scanf("%d %d", &u, &v);

adj[u][size[u]++] = v;
adj[v][size[v]++] = u;
}
int totalCost = 0;
// If roads are expensive
if(c_road >= c_lib) {

totalCost = n * c_lib;
}
else {
// Find connected components
for(int i = 1; i <= n; i++) {
if(!visited[i]) {
int cities = dfs(i);
// 1 library
totalCost += c_lib;
// roads for remaining cities
totalCost += (cities - 1) * c_road;
}
}
}
printf("%d\n", totalCost);
}
return 0;
}
Problem 3 - Selecting Diverse Astronauts for a Lunar Mission
#include <stdio.h>
#define MAX 100

int adj[MAX][MAX];
int size[MAX];
int visited[MAX];

// DFS function
int dfs(int node) {
visited[node] = 1;
int count = 1;
for(int i = 0; i < size[node]; i++) {
int next = adj[node][i];
if(!visited[next]) {
count += dfs(next);
}
}
return count;
}
int main() {
int n, p;
scanf("%d %d", &n, &p);

// Input graph
for(int i = 0; i < p; i++) {
int u, v;
scanf("%d %d", &u, &v);
adj[u][size[u]++] = v;
adj[v][size[v]++] = u;
}

int component[MAX];
int components = 0;
// Find connected components
for(int i = 0; i < n; i++) {
if(!visited[i]) {
component[components++] = dfs(i);
}
}

// Count valid pairs


int answer = 0;
int sum = 0;
for(int i = 0; i < components; i++) {
answer += component[i] * sum;
sum += component[i];
}
printf("%d", answer);
return 0;
}
Challenges Problems
Problem 1 - Shortest Route Finder in a City
#include <stdio.h>
#define MAX 100

int adj[MAX][MAX];
int size[MAX];

int queue[MAX];
int visited[MAX];
int distanceArr[MAX];

// BFS function
void bfs(int start, int n) {
int front = 0;
int rear = 0;
queue[rear++] = start;
visited[start] = 1;
distanceArr[start] = 0;

while(front < rear) {


int node = queue[front++];
for(int i = 0; i < size[node]; i++) {
int next = adj[node][i];
if(!visited[next]) {
visited[next] = 1;
distanceArr[next] = distanceArr[node] + 6;
queue[rear++] = next;
}
}
}
}
int main() {
int q;
scanf("%d", &q);
while(q--) {
int n, m;
scanf("%d %d", &n, &m);
// Reset arrays
for(int i = 1; i <= n; i++) {
size[i] = 0;
visited[i] = 0;
distanceArr[i] = -1;
}
// Input graph
for(int i = 0; i < m; i++) {
int u, v;
scanf("%d %d", &u, &v);
adj[u][size[u]++] = v;
adj[v][size[v]++] = u;
}
int start;
scanf("%d", &start);
bfs(start, n);

// Print distances
for(int i = 1; i <= n; i++) {
if(i != start) {
printf("%d ", distanceArr[i]);
}
}
printf("\n");
}
return 0;
}

Problem 2 - Edge Removal for Connected Components

#include <stdio.h>
#define MAX 100

int adj[MAX][MAX];
int size[MAX];
int visited[MAX];

// DFS function
void dfs(int node) {
visited[node] = 1;
for(int i = 0; i < size[node]; i++) {
int next = adj[node][i];
if(!visited[next]) {
dfs(next);
}
}
}

int main() {
int n, m, k;
scanf("%d %d %d", &n, &m, &k);

// Input graph
for(int i = 0; i < m; i++) {
int u, v;
scanf("%d %d", &u, &v);
adj[u][size[u]++] = v;
adj[v][size[v]++] = u;
}
int components = 0;

// Find connected components


for(int i = 1; i <= n; i++) {
if(!visited[i]) {
dfs(i);
components++;
}
}
// Impossible case
if(components > k) {
printf("-1");
}
else {
int removable = m - (n - k);
printf("%d", removable);
}
return 0;
}

You might also like