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;
	}