Snapchat 电面

1. 数独VERIFIER
2.判断一个图是不是
   bipartite:

   static class Node {

                public Node() {

                        neighbors = new HashSet<Node>();

                }

                Set<Node> neighbors;

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

                g.addEdge(a, b);

                g.addEdge(b, c);

                g.addEdge(c, a);

                System.out.println("is bipartite: " + g.isBipartite());

        }

求问楼主第二题是怎么做的呢？

kelvinzhong 发表于 2015-10-5 01:20
求问楼主第二题是怎么做的呢？

BFS + 染色

大腿NB！

majiamajia 发表于 2015-10-5 02:44
BFS + 染色

正解。DFS也可以。

DFS代码比较简洁

1.         public boolean isBipartite() {
   
2.             // implement here
   
3.             int len = nodes.size();
   
4.             if (len < 3) return true;
   
5.             Set<Node> first = new HashSet();    // always point to
   
6.             Set<Node> second = new HashSet();
   
7.             for (Node nd : nodes){
   
8.                 if (first.contains(nd) || second.contains(nd)) continue;
   
9.                 if (!addToSet(nd, first, second)) return false;
   
10.             }
    
11.             return true;
    
12.         }
    
13.         
    
14.         boolean addToSet(Node nd, Set<Node> first, Set<Node> second){
    
15.             if (second.contains(nd)) return false;
    
16.             if (first.contains(nd)) return true;
    
17.             first.add(nd);
    
18.             for(Node child : nd.neighbors){
    
19.                 if (!addToSet(child, second, first)) return false;
    
20.             }
    
21.             return true;
    
22.         }
    
23.     }

复制代码

majiamajia 发表于 2015-10-5 02:44
BFS + 染色

楼主，求详细代码啊，怎么染色啊？

majiamajia 发表于 2015-10-5 02:44
BFS + 染色

垅主好腻害！！！！