COLGQU - Editorial

editorial
, , ,
1

COLGQU - Editorial

Problem Link:

Practice

Contest

Author, Tester and Editorialist:-
tejaram15

Difficulty:

Easy

Pre-Requisites:

Dfs , Graph traversal , (Union-Find Data structure)** Optional

Problem Statement:

Given a graph G with N nodes and M edges with specific id's. Find number of id's that connect an edge X to another edge Y. There may be a direct link or an indirect link too.

Explanation:

Since the number of queries are not too big so a dfs can be run for all the queries.
bool dfs(int v,int col,int dst){ //v is the source and dst is destination 
vis[v]=1;		//with col as the colour

if(v==dst) return 1;

for(int i=0;i<(int)adjlst[v].size();i++){

	int e = adjlst[v][i].first;

	int f = adjlst[v][i].second;

	if(f==col && !vis[e]){

		if(dfs(e,col,dst)) return true;

	}

}

return false;

}

Alternatively, Union-find data structure can be used to store nodes connected with same colours.

Create an array of objects where index will be colour and operation will be the union of two nodes.

Finally when queried check for every color if there exists a set which is the union of both u and v i.e. u and v should be in the same set for the same colour.

UnionFind UF[105]; 
REP(i,100) UF[i].init(n);

REP(i,m){

	int a,b,c;

	cin>>a>>b>>c;

	--a;--b;--c;

	UF[c].unionSet(a,b);

}

int q;

cin>>q;

REP(x,q){

	int res=0;

	int u,v;

	cin>>u>>v;

	--u;--v;

	REP(i,100) if(UF[i].isSameSet(u,v)) res++;

	printf("%d\n",res);

}

Union find is a class with the following methods:-

  1. Make set
  2. Union set
  3. Find set
Time Complexity: O(N)

Solution : Dfs Solution OR Union Find Solution

2

Very weak test cases, even the one provided for checking are not checked.

3

the trick in the problem was to check for each and every id’s …
&& for the correction :: it is given that bi>ai so how could 5 5 1 and 6 6 5 be the inputs in the first test case

4

why for a graph 1—2----3 (let wt = 4 and 5 )
the query 1 3 is giving answer 0 …
it should be 1 . .
and the graph 1—2---3 (with wt 1 and 1 )
for query 1 and 3 is giving answer 1…
but why ??