The most detailed and deep dived explanation to this problem you will ever find. Hope you will like it. Please find all the code below : //Approach-1 (DFS) Using vector as map //Approach-2 (DFS) (Using unordered_map) //Approach-3 (BFS) Using vector as map //Approach-4 (BFS) (Using unordered_map) Link : github.com/MAZHARMIK/Interview_DS_Algo/blob/master/Graph/Clone%20Graph.cpp
Ye channel bahut aage jane vale h.. bahut bawal samjhata h ye bhai 😍bhai bs bata do kon sa aap use karte ho drawing ke liye .. main bhi install kar lunga..interview me bada proplem hota h diagram vagairh bana ke show karne me
why you wrote map.clear() at the beginning of the function ? whereas we hadn't put any value in the map we just declared it globally? BTW great content ❤✌✌
Hi abhi, Thanks a lot for your appreciation. Actually multiple calls for the function is made. So we don’t want stale entries in the map to be there when a new call is made to the function. But most of the time , even if you don’t clear it, the solution works. But it’s a good practice to do that.
bro u are great at explaining things but u should change ur channel name to a short and simple name, so that we can also recommend ur channel to others as ur current name is slightly difficult to remember
I really appreciate your suggestion ❤️❤️❤️ I will plan to change it to CSM (Code Story With MIK). Right now, my Instagram, linkedIn and , Facebook all have this name and hence might take time to migrate. Thank you so much for your precious suggestions and watching my videos ❤️❤️❤️
Java Solution /* // Definition for a Node. class Node { public int val; public List neighbors; public Node() { val = 0; neighbors = new ArrayList(); } public Node(int _val) { val = _val; neighbors = new ArrayList(); } public Node(int _val, ArrayList _neighbors) { val = _val; neighbors = _neighbors; } } */ class Solution { public Node cloneGraph(Node node) {
class Solution{ Node cloneGraph(Node node){ Node temp = new Node(node.val); //ab clone krna h recursively iske neighbours ko // saath me ek map bna lete hain taaki koi node bn gya h // to dubara nahi bnega //map ek purana node usk corresponding new node jo //hmne bnaya Map map = new HashMap(); map.put(node,temp); DFS(node,temp,map); return temp; } void DFS(Node node,Node temp,Map map) { //original node k neighbours dhund kr clone krte jaao for(Node neigh : node.neighbors) { // ab do case ya to clone hua hoga ya to nai if(!map.containsKey(neigh)) { Node cloneNeigh = new Node(neigh.val); map.put(neigh,cloneNeigh); temp.neighbors.add(cloneNeigh); DFS(neigh,cloneNeigh,map); } else { temp.neighbors.add(map.get(neigh)); } } } }
Graph was very tough for me but because of your graph concepts playlist today I can solve most of the graph questions easily. Thanks a Lot 😊
You made my day ❤️❤️❤️
@@codestorywithMIK Keep going this channel future is very bright !!!
Thank you so much Shivansh ❤️❤️❤️
prooved
@@shivanshchauhan52
The most detailed and deep dived explanation to this problem you will ever find. Hope you will like it.
Please find all the code below :
//Approach-1 (DFS) Using vector as map
//Approach-2 (DFS) (Using unordered_map)
//Approach-3 (BFS) Using vector as map
//Approach-4 (BFS) (Using unordered_map)
Link : github.com/MAZHARMIK/Interview_DS_Algo/blob/master/Graph/Clone%20Graph.cpp
The best one bro. I am speechless
speechless with this masterpiece
Yaar bhaiya kya padhaya hai aapne ...........dil khush kar diya
Thank you 🙏❤️😇
Outstanding bhai! You prove every time why you are the undisputed graph king 👑💙💙
Thank you so much JJ
Thank you , Amazing explanation.
Awesome after listing story of 20 minutes write code by own🥳
16:59 ---> That's one of the reasons I come to your channel. I am always sure that I will understand more from your explanations.
Was able to do today's question without any help, but still here just to like the video. Amazing channel and well structured videos!
Solved today's GFG POTD after watching this video thank you so much bhaiya ❤❤
Awesome ❤️❤️
Awesome !! Worth watching 41mins
Thank you so much for watching 😇❤️🙏
Never regret watching your explanation videos.❤
Thanks again sir. Here are the Java implementations of your BFS and DFS approaches -:
BFS CODE :
class Solution {
Map map;
public Node cloneGraph(Node node) {
map = new HashMap();
if(node == null)
return null;
Node clone = new Node(node.val);
map.put(node, clone);
Queue q = new ArrayDeque();
q.add(node);
while(!q.isEmpty()){
Node curr = q.poll();
Node currClone = map.get(curr);
for(Node n : curr.neighbors){
if(!map.containsKey(n)){
Node c = new Node(n.val);
map.put(n, c);
currClone.neighbors.add(c);
q.add(n);
}
else
currClone.neighbors.add(map.get(n));
}
}
return clone;
}
}
----------------------------------------------------------------------------------------------------
DFS CODE :
class Solution {
Map map;
public Node cloneGraph(Node node) {
map = new HashMap();
if(node == null)
return null;
Node clone = new Node(node.val);
map.put(node, clone);
dfs(node, clone);
return clone;
}
private void dfs(Node node, Node clone){
for(Node n : node.neighbors){
if(!map.containsKey(n)){
Node curr = new Node(n.val);
map.put(n, curr);
clone.neighbors.add(curr);
dfs(n, curr);
}
else
clone.neighbors.add(map.get(n));
}
}
}
Thank you so so much
Means a lot to me ❤️
Great Explanation Makes the question very easy to understand and not only graph u make easy dp also
ThankU for best Explanation
Really great explanation
thanks a lot, bhaiya, nice explanations, are easy to understand.
bhai kyu padhate hon itna badhiya 😍
Means a lot ❤️😇
The K.I.N.G of Graphs
so true!
Thanks a lot
Ye channel bahut aage jane vale h.. bahut bawal samjhata h ye bhai 😍bhai bs bata do kon sa aap use karte ho drawing ke liye .. main bhi install kar lunga..interview me bada proplem hota h diagram vagairh bana ke show karne me
Hi there
I use default notes app ❤️🙏
Thank you ☺️
A message to new comers to this channel - "Graph is Hard until you watch codestorywithMIK"
Shi Haai bhai
i love you bro
why you wrote map.clear() at the beginning of the function ? whereas we hadn't put any value in the map we just declared it globally?
BTW great content ❤✌✌
Hi abhi,
Thanks a lot for your appreciation.
Actually multiple calls for the function is made. So we don’t want stale entries in the map to be there when a new call is made to the function.
But most of the time , even if you don’t clear it, the solution works.
But it’s a good practice to do that.
Bhaiya it's showing your github page is not available.. and btw thank you for wonderfull explainantion..
Sorry for the typo.
Link corrected.
github.com/MAZHARMIK/Interview_DS_Algo/blob/master/Graph/Clone%20Graph.cpp
bro u are great at explaining things but u should change ur channel name to a short and simple name, so that we can also recommend ur channel to others as ur current name is slightly difficult to remember
I really appreciate your suggestion ❤️❤️❤️
I will plan to change it to CSM (Code Story With MIK).
Right now, my Instagram, linkedIn and , Facebook all have this name and hence might take time to migrate.
Thank you so much for your precious suggestions and watching my videos ❤️❤️❤️
❤❤❤❤
❤️🙏 Means a lot 😇
Sir java ka code bhi explain krr
github link in the description for this problem has a typo its a space instead of underscore so %20 instead of _
Thank you so much Yash. Corrected now.
github.com/MAZHARMIK/Interview_DS_Algo/blob/master/Graph/Clone%20Graph.cpp
❤
Java Solution
/*
// Definition for a Node.
class Node {
public int val;
public List neighbors;
public Node() {
val = 0;
neighbors = new ArrayList();
}
public Node(int _val) {
val = _val;
neighbors = new ArrayList();
}
public Node(int _val, ArrayList _neighbors) {
val = _val;
neighbors = _neighbors;
}
}
*/
class Solution {
public Node cloneGraph(Node node) {
if(node == null) return node ;
Node clone = new Node(node.val) ;
HashMap map = new HashMap() ;
map.put(node,clone) ;
DFS(node,clone,map) ;
return clone ;
}
public static void DFS(Node org , Node clone , HashMap map){
for(Node neigh : org.neighbors){
if(!map.containsKey(neigh)){
Node tempNode = new Node(neigh.val) ;
clone.neighbors.add(tempNode) ;
map.put(neigh,tempNode) ;
DFS(neigh,tempNode,map) ;
}
else{
clone.neighbors.add(map.get(neigh));
}
}
}
}
do like if it helped.
Error is coming while opening ur github:(
Link corrected. Can you try again please
github.com/MAZHARMIK/Interview_DS_Algo/blob/master/Graph/Clone%20Graph.cpp
Hogya bhai ye, recursion + map, time laga thoda dimag lagane me, @mik bhai aapne competetive programming ki hai kya :
unordered_map m;
Node* cloneGraph(Node* node) {
if(!node)return node;
Node* root= new Node(node->val);
vector v;
m[node]=root;
for( auto x : node->neighbors){
if(m.find(x)==m.end()){
v.push_back(cloneGraph(x));
}
else{
v.push_back(m[x]);
}
}
root->neighbors=v;
return root;
}
Hi Kartik,
No, i have not done much in Competitive Coding. But would love to try
Thanks Mike for efforts :)
Please find below Java Code -
class Solution {
Map map = new HashMap();
public Node cloneGraph(Node node) {
if(node == null){
return null;
}
Node clone_node = new Node(node.val);
map.put(node, clone_node);
dfs_traversal(node, clone_node);
return clone_node;
}
void dfs_traversal(Node node, Node clone_node){
for(Node n : node.neighbors){
if(!map.containsKey(n)){
Node clone = new Node(n.val);
map.put(n, clone);
clone_node.neighbors.add(clone);
dfs_traversal(n, clone);
}
else{
clone_node.neighbors.add(map.get(n));
}
}
}
}
Why is my comment getting removed?😮
tried several times to paste the Java code but it is getting removed every time automatically 😥😥
Hi JJ
Can you try again. I am also not sure why this is happening
Was waiting for your java code bro
@@codestorywithMIK @asimzohr2293 added, hoping it does not get removed
@@codestorywithMIK it got removed again it seems 😐
iska iterative dfs ka solution h kisi k pass to please send
unordered_map mp;
void dfs(Node* node){
Node* temp = new Node(node->val);
mp[node] = temp;
for(auto it : node->neighbors){
if(mp.find(it) != mp.end()) temp->neighbors.push_back(mp[it]);
else {
dfs(it);
temp->neighbors.push_back(mp[it]);
}
}
}
Node* cloneGraph(Node* node) {
if(!node) return NULL;
dfs(node);
return mp[node];
}
class Solution{
Node cloneGraph(Node node){
Node temp = new Node(node.val);
//ab clone krna h recursively iske neighbours ko
// saath me ek map bna lete hain taaki koi node bn gya h
// to dubara nahi bnega
//map ek purana node usk corresponding new node jo
//hmne bnaya
Map map = new HashMap();
map.put(node,temp);
DFS(node,temp,map);
return temp;
}
void DFS(Node node,Node temp,Map map)
{
//original node k neighbours dhund kr clone krte jaao
for(Node neigh : node.neighbors)
{
// ab do case ya to clone hua hoga ya to nai
if(!map.containsKey(neigh))
{
Node cloneNeigh = new Node(neigh.val);
map.put(neigh,cloneNeigh);
temp.neighbors.add(cloneNeigh);
DFS(neigh,cloneNeigh,map);
}
else
{
temp.neighbors.add(map.get(neigh));
}
}
}
}
Java Implementation
class Solution
{
HashMap mp = new HashMap();
void DFS(Node node, Node clone_node)
{
for (Node n : node.neighbors)
{
if (!mp.containsKey(n))
{
Node clone = new Node(n.val);
mp.put(n, clone);
clone_node.neighbors.add(clone);
DFS(n, clone);
}
else
{
clone_node.neighbors.add(mp.get(n));
}
}
}
Node cloneGraph(Node node)
{
if (node == null)
{
return null;
}
mp.clear();
Node clone_node = new Node(node.val);
mp.put(node, clone_node);
DFS(node, clone_node);
return clone_node;
}
}
class Solution {
Node cloneGraph(Node node){
Node st=node;
HashSetvis=new HashSet();
HashMapmpp=new HashMap();
dfs(st,vis,mpp);
addEdges(mpp);
return mpp.get(st);
}
public static void addEdges(HashMapmpp){
for(Map.Entery e:mpp.entrySet()){
Node u=(Node)e.getKey();
mpp.get(e.getKey()).neighbors.add(u);
}
}
public void dfs(Node st,HashSetvis,HashMapmpp){
vis.add(st);
Node copyNode=new Node(st.val);
mpp.put(st,copyNode);
for(Node v:st.neighbors){
if(!vis.contains(v))
dfs(v,vis,mpp);
}
}
}
🎉❤