In a company's OA, I came across the question of counting all cycles in a graph and used the coloring method. Can anybody tell me how to improvise this solution so I can count a cycle that includes a node that's part of more than two cycles?
void dfs(int s,int p,vector<int> &color,vector<int> &parent){
if(color[s]==2)return;
if(color[s]==1){
int cur=p;
vector<int> vec;
ans++; // count of cycles
vec.push_back(cur);
while(cur!=s){
cur=parent[cur];
vec.push_back(cur);
}
cycles.push_back(vec); // to store answer
return ;
}
parent[s]=p;
color[s]=1;
for(auto &val:graph[s]){
if(val!=p){
dfs(val,s,color,parent);
}
}
color[s]=2;
return;
}
Output for addEdge(1,4);
addEdge(1,2); addEdge(1,3); addEdge(3,4); addEdge(2,3); is {3, 4, 1} and {2, 3, 4, 1}.
but for this one addEdge(1,2); addEdge(1,4); addEdge(1,3); addEdge(3,4); addEdge(2,3); is {3, 2, 1} and {4, 3, 2, 1}.
I just changed the order. Nothing else graph's structure is still the same.