Graph Data Structures Practice Problems With Hints

Graph Data Structures Problems

Here are the problems you can practice on Graphs:

1. UVa 00599 - The Forrest for the Trees.

2. UVa 10895 - Matrix Transpose

3. UVa 10928 - My Dear Neighbours

4. UVa 11550 - Demanding Dilemma

5. UVa 11991 - Easy Problems from Rujia Liu?

Here is the link to these problems:

https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=635

Here are my solutions and hints to some of these problems.

Solution and hints

UVa 11991 Easy Problems from Rujia Liu?

Simple. Create an Adjacency matrix.

#include <bits/stdc++.h>
	using namespace std;
	int main(int argc, char const *argv[]) {
	int n, m, d, k;
	vector<vector<int> > v;
	while (scanf("%d %d",&n, &m)!=EOF){
	v.assign(1000000, vector<int>()); ///////The elements can go at most upto 1000000
	int d;
	for (size_t i = 1; i <= n; i++) {
	scanf("%d\n", &d);
	v[d].push_back(i);
	}
	for(int i=0;i<m;i++){
	scanf("%d %d", &k, &d);
	if(k-1<v[d].size())
	printf("%d\n", v[d][k-1]);
	else
	printf("%d\n",0);
	}
	}
	return 0;
	}

Uva 10895 Matrix Transpose

Simple. You just need to reverse the rows and columns when inputting the data. Store this in some other container. And once done spit it out :P

#include <bits/stdc++.h>
	using namespace std;
	int main(int argc, char const *argv[]) {
	int m,n;
	while(scanf("%d %d\n", &m, &n)!=EOF){
	vector<vector<pair<int, int> > > ans;
	ans.assign(n, vector<pair<int, int> >());
	for (int i = 0; i < m; i++) {
	int r;
	scanf("%d", &r);
	int col[r];
	int value[r];
	for (int j = 0; j < r; j++) {
	scanf("%d", &col[j]);
	col[j] -=1;
	}
	for (int j = 0; j < r; j++) {
	scanf("%d", &value[j]);
	}
	for (int j = 0; j < r; j++) {
	ans[col[j]].push_back(make_pair(i+1,value[j]));
	}
	}
	cout<<n<<" "<<m<<endl;
	for (int j = 0; j < n; j++) {
	cout<<ans[j].size();
	for (int k = 0; k < ans[j].size(); k++) {
	cout<<" "<<ans[j][k].first;
	}
	cout<<endl;
	// cout<<ans[j][0].second;
	// cout<<ans[j][1].second;
	for (size_t l = 0; l < ans[j].size(); l++) {
	if(l!=0)
	cout<<" ";
	cout<<ans[j][l].second;
	}
	cout<<endl;
	}
	}
	return 0;
	}

Forests, Trees and Graphs

Some basic terminologies of Graphs: Trees, Forests, acorns

Recall the definition of graphs:

A graph G is a set of point VG), along with a set of edges E(G), where each element of E(G) is an unordered pair of distinct points of V(G).

Cycle

If you draw the graph and you see a closed-loop in it. The loop is called a "cycle".

Tree

A graph devoid of cycles is called a tree.

Path

A path in a graph G is an alternating sequence of points and edges, such that all the points of the path are distinct.

Every two points of a tree are joined by a unique path.

Connected Graphs

A graph is called connected if every pair of points are joined by a path. If the graph is not connected then it is made up of "subgraphs". These subgraphs are called as connected components of the graph G.

Forests

A graph for which each connected component is a tree is called a forest.

Acorn

In the forest when one of the component trees has one point but no edges joined to it. That is, it is an isolated dot. This is called an acorn.

Binary Indexed (Fenwick) Tree

Binary Indexed (Fenwick) Tree

Fenwick Tree is also known as Binary Indexed Tree (BIT).

The Fenwick Tree is a useful data structure for implementing dynamic cumulative frequency tables.

For example:

Suppose we have test scores of m=11 students $f = {2,4,5,5,6,6,6,7,7,8,9}$. The test scores are integer values ranging from [1..10].

We define the term frequency and cumulative frequency as follows.

The frequency of a test score is the number of times it is appearing in the table. The cumulative frequency of a test score is the sum of frequencies of all the test scores up to that test score. 

We can draw the table indicating these as follows:

       Index/Score         Frequency        Cumulative Frequency cf                      

              0            |             -                    |                   -                                        

              1            |             0                   |                   0                                        

              2            |             1                   |                   1                                        

              3            |             0                   |                   1                                        

              4            |             1                   |                   2                                        

              5            |             2                   |                   4                                        

              6            |             3                   |                   7                                        

              7            |             2                   |                   9                                        

              8            |             1                   |                  10                                        

              9            |             1                   |                  11                                       

            10            |             0                   |                  11

The cumulative frequency table can also be used as a solution to the Range Sum Query (RSQ) as discussed at the end of this post: https://rishabhjainiitbhu.blogspot.com/2019/09/segment-trees.html

When the frequencies are static, then the cumulative frequency table can be computed with a simple O(n) loop.

However, when the frequencies are frequently updated (increased or decreased) we use a dynamic data structure.

Instead of using Segment trees we use far simpler Fenwick Tree. Fenwick Tree operations are extremely efficient as they use fast bit manipulation techniques.

We will use the function LSOne(i) (which is: i & (-i) ). LSOne(i) returns the Least Significant One-bit in i. That is it will return the number where the first one bit is in i.
If i is 101100101000 than LSOne will give 1000.

We use vector for implementing Fenwick Tree.

The Fenwick Tree is a tree that is indexed by the bits of its integer keys. These integer keys fall within the range [1 .. n] skipping index 0. In the above table [1 .. 10] are the integer keys in the corresponding array with size n=10 and m=11 data points.

Let the Fenwick Tree be named as ft. ft[i] stores the cumulative frequency of elements.

The element at index i is responsible for elements in the range [i-LSOne(i)+1 .. i]. Thus, ft[i] stores the cumulative frequency of elements {i-LSOne(i)+1, i-LSOne(i)+2 .. i}. For above array ft[4]=2 is responsible for the range [4-4+1 .. 4] = [1 .. 4], ft[6]=5 is responsible for range [6-2+1 .. 6] = [5 .. 6], so on and so forth.

                              {---------------------------------------------------------}10
                               {--------------------}2                                                |
                             {------}1                   |          {---------}5                     |          {------}1
                             0          |        0          |           2           |           2           |          1          |
                              |          |         |          |           |             |           |            |          |           |       
Index/Key:  0        1        2        3          4          5          6         7           8         9         10
In Binary   0000  0001  0010  0011   0100    0101     0110    0111    1000    1001   1010
Freq(cum) 0(0)    0(0)   1(1)    0(1)     1(2)     2(4)     3(7)       2(9)      1(10)   1(11)   0(11)

{---} denotes the ranges

With such an arrangement, if we want to obtain the cumulative frequency between [1 .. b], i.e. rsq(b), we simply add ft[b], ft[b'], ft[b''] .. until $b^i$ is zero.

Here b' = b - LSOne(b). This strips off the least significant one-bit of b at each step. An integer has only O(log b) bits, rsq(b) runs O(log n) times, when b=n.

Try drawing diagram for the above tree. rsq(6) = ft[6] + ft[4], this because the indices 4 and 6 are responsible for range [1 .. 4] and [5 .. 6] respectively. By combining them, we account for the entire range of [1 .. 6].

With rsq(b) available, obtaining the cumulative frequency between two indices [a..b] where a!=1 is simple, rsq(a,b) = rsq(b)-rsq(a-1). This is also an O(logn) time task when b=n.

Updating
Updating the value of the element at index k by adjusting its value by v, i.e. calling adjust(k,v) we have to update ft[k], ft[k'], ft[k''].... until $k^i$ exceeds n. But this time k' = k + LSOne(k). If you adjust(k,v) it will add 1 to ft[k] at indices k=5=101, k'=(101)+(001)=110 and k''=(110)
+(010)=1000=8 via the expression given above.

Notice that if you project a line upwards from index 5 in the figure, the line intersects that ranges under the responsibility of index 5, index 6, and index 8.


Fenwick tree thus supports both RSQ and update operations in just O(n) space complexity and O(logn) time complexity, given a set of m integer keys that ranges from [1 .. n]. This makes Fenwick Tree an ideal DS for solving dynamic RSQ problems.


Here is the code for Fenwick Tree

#include <bits/stdc++.h>
	using namespace std;
	typedef vector<int> vi;
	class FenWickTree{
	private: vi ft;
	public: FenWickTree(int n){
	ft.assign(n+1, 0);
	}
	int LSOne(int b){
	return b&-b;
	}
	int rsq(int b){
	int sum=0;
	for (; b; b-=LSOne(b)) {
	sum += ft[b];
	}
	return sum;
	}
	int rsq(int a, int b){
	return rsq(b)-(a==1?0:rsq(a-1));
	}
	void adjust(int k, int v){
	for(;k<(int)ft.size();k+=LSOne(k)){
	ft[k] += v;
	}
	}
	};
	int main(int argc, char const *argv[]) {
	int f[] = { 2,4,5,5,6,6,6,7,7,8,9 }; // m = 11 scores
	FenWickTree ft(10);
	for (int i = 0; i < 11; i++) ft.adjust(f[i], 1); // this is O(k log n)
	printf("%d\n", ft.rsq(1, 1)); // 0 => ft[1] = 0
	printf("%d\n", ft.rsq(1, 2)); // 1 => ft[2] = 1
	printf("%d\n", ft.rsq(1, 6)); // 7 => ft[6] + ft[4] = 5 + 2 = 7
	printf("%d\n", ft.rsq(1, 10)); // 11 => ft[10] + ft[8] = 1 + 10 = 11
	printf("%d\n", ft.rsq(3, 6)); // 6 => rsq(1, 6) - rsq(1, 2) = 7 - 1
	ft.adjust(5, 2); // update demo
	printf("%d\n", ft.rsq(1, 10)); // now 13``
	return 0;
	}

Grab a pencil and draw the things out.