## COLGQU - Editorial

### Problem Link:

PracticeContest

**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]*.first;

int f = adjlst[v]*.second;

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

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

}

}

return false;

}

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]*.first;

int f = adjlst[v]*.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*.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*.isSameSet(u,v)) res++;

printf("%d ",res);

}

REP(i,100) UF*.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*.isSameSet(u,v)) res++;

printf("%d ",res);

}

Union find is a class with the following methods:-

- Make set
- Union set
- Find set

**Time Complexity:**

**O(N)**

Solution : Dfs Solution OR Union Find Solution