ES242. Data Structures and Algorithms I. Week 04 Lab

ES242. Data Structures and Algorithms I.

Lab 04

Back to course page

Theme: Graph Representations and Euler Tours

The goal of this exercise is to:

  1. Read a graph and store it as an adjacency matrix.
  2. Return the largest degree, that is to say, return max(d(v)) over all vertices v in the graph G.


You can visualize the execution of a simplified version of the template code here.

Input

The first line of input is two space-separated integers n and m, denoting the number of vertices and edges of G, respectively. Vertices are indexed from 0 to n-1.

The next m lines of code are two space separated integers u and v in the range 0 and n-1, indicating an (undirected) edge between vertices u and v.

Output

The output is a single integer, corresponding to the maximum degree of the graph.

Sample I/O

Sample Input

5 4
0 1
0 2
0 3
0 4

Sample Output

4

Template Code

// Adjacency Matrix representation in C
#include <stdio.h>

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

  int m;
  scanf("%d", &m);

  int G[n][n];
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      G[i][j] = 0;

  for (int i = 0; i < m; i++) {
    // Write the logic to read the endpoints of the edge here.
    // ...
    
    // Write the logic to add the edge just read next.
    // ...
  }

  int maxdegree = 0;

  // Write the logic to print the maxdegree of the graph here.
  // ...

  printf("%d", maxdegree);
  return 0;

}

In this exercise your goal is to implement a graph as an adjacency list and determine, given a pair of vertices u and v, the number of common nieghbors that they have: that is, the number of vertices w such that w is adjacent to u AND w is adjacent to v (note that w is not equal to either u or v).

You can visualize the execution of a simplified version of the template code here.

Input

The first line of input is two space-separated integers n and m, denoting the number of vertices and edges of G, respectively. Vertices are indexed from 0 to n-1.

The next m lines of code are two space separated integers u and v in the range 0 and n-1, indicating an (undirected) edge between vertices u and v.

The last line is a pair of space-separated integers x and y.

Output

The output is a single integer, corresponding to the number of common neighbors of x and y.

Sample I/O

Sample Input

6 8
0 1
0 2
0 3
0 4
5 1
5 2
5 3
5 4
0 5

Sample Output

4

Template Code

#include <stdio.h>
#include <stdlib.h>

// A structure to represent an adjacency list node
struct AdjListNode {
  int vertex;
  struct AdjListNode *next;
};

// A structure to represent a graph. A graph is an array of adjacency lists.
// Size of array will be V (number of vertices in graph)
struct Graph {
  int n;
  struct AdjListNode* vertices;
};

// A utility function to create a new adjacency list node
struct AdjListNode* newAdjListNode(int v) {
  struct AdjListNode *newNode =
      (struct AdjListNode *)malloc(sizeof(struct AdjListNode));
  newNode->vertex = v;
  newNode->next = NULL;
  return newNode;
}

// A utility function that creates a graph of V vertices
struct Graph *createGraph(int V) {
  struct Graph *graph = (struct Graph*)malloc(sizeof(struct Graph));
  graph->n = V;
  
  graph->vertices = (struct AdjListNode*) malloc(V * sizeof(struct AdjListNode));
  int i;
  for (i = 0; i < V; ++i){
    graph->vertices[i].next = NULL;
    graph->vertices[i].vertex = -1;
  }

  return graph;
}

// Adds an edge to an undirected graph
void addEdge(struct Graph *graph, int src, int dest) {
  // Add an edge from src to dest.  A new node is added to the adjacency
  // list of src.  The node is added at the begining
  struct AdjListNode *newNode = newAdjListNode(dest);
  newNode->next = graph->vertices[src].next;
  graph->vertices[src].next = newNode;

  // Since graph is undirected, add an edge from dest to src also. Write this part below.
  // ...
}

int main() {

  int n;
  scanf("%d", &n);

  struct Graph *G = createGraph(n);

  int m;
  scanf("%d", &m);

  for (int i = 0; i < m; i++) {
    int u, v;
    scanf("%d", &u);
    scanf("%d", &v);
    addEdge(G, u, v);
  }

  int x, y;
  
  scanf("%d %d", &x, &y);

  // Write your solution here.
  
  return 0;
}

You have to store the edges of a given graph as an edge list, and compute the degree of a given vertex.

For understanding how the template code works refer to this execution on a hard-coded example.

Input

The first line contains a number m, which is the number of edges in the graph G.

The next m lines contain two space-separated integers represnting the endpoints of the edges.

The last line contains a single integer k.

Output

The task is to report the degree of the vertex k, that is, the number of edges for which k is one of the endpoints.

Sample I/O

Sample Input

6
1 3
2 1
5 3
1 7
1 8
2 5
1

Sample Output

4

Template Code

#include <stdio.h>

// Declare a datatype that stores a single edge.

struct SingleEdge {
  int ep[2];
  struct SingleEdge *nextedge;
};

int main(void) {

  // To begin with, there was nothing.
  struct SingleEdge *head = NULL;
  head = (struct SingleEdge *)malloc(sizeof(struct SingleEdge));

  struct SingleEdge *current = NULL;
  current = (struct SingleEdge *)malloc(sizeof(struct SingleEdge));

  // head simply points to the first element of the list.
  // current will move forward as things get added.

  head->ep[0] = -1;
  head->ep[1] = -1;
  head->nextedge = current;

  // Read the number of edges.

  int m;
  scanf("%d", &m);

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

    struct SingleEdge *newedge;

    newedge = (struct SingleEdge *)malloc(sizeof(struct SingleEdge));

    // Populate the newedge struct
    // with information about the current edge.

    current->nextedge = newedge;
    current = newedge;
  }

  struct SingleEdge *navigator = head->nextedge;
  int degree = 0;
  int vertex;

  scanf("%d", &vertex);

  while (navigator) {
    // CHECK IF "vertex" is an endpoint
    // of the current edge being explored.
    if (...) {
      degree = degree + 1;
    }
    navigator = navigator->nextedge;
  }

  printf("%d", degree);

  return 0;
}

Given a simple (no selfloops or multiedges), connected (any two vertices are reachable from each other), and undirected (no edge orientations) graph as input, return YES if it has a Euler path OR circuit, and NO otherwise.

You may assume the following:

  • An undirected graph has an Eulerian cycle if and only if every vertex has even degree, and all of its vertices with nonzero degree belong to a single connected component.

  • An undirected graph has an Eulerian path if and only if exactly zero or two vertices have odd degree, and all of its vertices with nonzero degree belong to a single connected component.

Input

The first line of input is two space-separated integers n and m, denoting the number of vertices and edges of G, respectively. Vertices are indexed from 0 to n-1.

The next m lines of code are two space separated integers u and v in the range 0 and n-1, indicating an (undirected) edge between vertices u and v.

Output

Output YES if it has a Euler path or circuit, and NO otherwise.

Sample I/O

Sample Input

10 6
1 3
2 1
5 3
1 7
1 8
2 5

Sample Output

YES

Imagine a grid country with nm axis-parallel highways (no kidding: check out this video about the U.S. interstate highway numbering system! - watching the video is not required for understanding this problem).

Of these highways, \(n\) are east-west and m are north-south. Note that the highways form an \((n - 1) \times (m - 1)\) grid. In order to control the traffic, a policy was enforced which involved making each highway one way.

This means in each east-west highway, the traffic moves from “left to right” or “right to left”. Also, traffic moves “top to bottom” or “bottom to top” in each highway that runs north-south. It is possible to enter a horizontal highway from a vertical highway, or vice versa, at their intersection.

A proposed set of orientations is given to you. You have to figure out if it is possible, after making the highways one-way based on these suggested orientations, if it is possible to reach any intersection from any other (without breaking traffic rules!)

Input

The first line of input contains two integers \(n\) and \(m\), denoting the number of east-west highways and the number of north-south highways.

The second line contains a string of length \(n\), made of characters ‘{’ and ‘}’, denoting direction of each horizontal highway. If the i-th character is equal to ‘{’, the highway is directed from right to left otherwise, the highway is directed from left to right. Highways are listed in order from top to bottom.

The third line contains a string of length m, made of characters ‘B’ and ‘T’, denoting direction of each vertical highway. If the i-th character is equal to ‘T’, the highway is directed from south to north (towards the top), and if it is ‘B’ the highway is directed from north to south (towards the bottom). Highways are listed in order from left to right.

Output

If the given pattern meets the mayor’s criteria, print a single line containing “YES”, otherwise print a single line containing “NO”.

Sample I/O

Sample Input

3 3
}{}
BTB

Sample Output

NO

Sample Input

4 6
{}{}
BTBTBT

Sample Output

YES

Let’s say that a vertex in a directed graph is balanced if its indegree is the same as its outdegree.

You are given a simple and undirected graph \(G\). An orientation of \(G\) is an assigment of a direction to every edge in \(G\).

You want to come up with an orientation that maximizes the number of balanced vertices.

Return the number of balanced vertices in a orientation that maximizes this number.

Input

The first line contains a positive integer \(t~(1 \leqslant t \leqslant 200)\) — the number of testsets in the input.

Each of the testsets is given in the following way.

The first line contains two integers \(n\) and \(m\) \((1 \leqslant n \leqslant 200, 0 \leqslant m \leqslant n·(n - 1) / 2)\) — the number of vertices and the number of edges in \(G\).

The next m lines contain the description of the edges. Each line contains two integers \(u\) and \(v\) \((1 \leqslant u, v \leqslant n)\) — the endpoints of the edge. It’s guaranteed that there are no self-loops and multiedges. It is possible that the graph is not connected.

Output

For each testset print the number of balanced vertices in an orientation that maximizes the number of balanced vertices.

Sample I/O

Sample Input

2
5 5
2 1
4 5
2 3
1 3
3 5
7 2
3 7
4 2

Sample Output

3
3

Here is an orientation of the first graph that has three balanced vertices:

1 3
3 5
5 4
3 2
2 1

In the second graph, no matter how the two edges are oriented, there will be four imbalanced and three balanced vertices.

List of Practice Problems

  1. Weird Journey - if you already know how to check if a graph is connected, go for this! Otherwise you could come back to it after learning BFS/DFS :)
  2. ROOKPATH - can you figure out how to model this problem as finding an Euler Tour?
  3. Mashtali: a Space Oddysey - at least one method of solving this question involves constructing an Euler tour (but it is less direct than the previous problem), revisit it once you have figured out how to.