COLGQU - Editorial
Problem Link:
PracticeAuthor, Tester and Editorialist:-
tejaram15
Difficulty:
EasyPre-Requisites:
Dfs , Graph traversal , (Union-Find Data structure)** OptionalProblem 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:-
- Make set
- Union set
- Find set
Solution : Dfs Solution OR Union Find Solution