886. Possible Bipartition 问题 求问代码错在哪里

Job Hunting CS News
1

楼主做这题的时候自己测试的时候数据能过但是一提交就出现

runtime error Line 346: Char 35: runtime error: member access within misaligned address 0x000300000001 for type ‘struct __node_type’, which requires 8 byte alignment (hashtable_policy.h)

自己去ide去调试也能得到正确答案不知道为什么 百思不得其解 希望指出我代码的问题。
楼主的思路是dfs，维持两个set one，two，如果one和two都满足要求就返回true。

class Solution {
public:
    bool isValid(unordered_set<int> group, vector<vector<int>>& dislikes){
        for(int i = 0; i< dislikes.size(); i++){
            int a = dislikes[i][0];
            int b = dislikes[i][1];
            if(group.count(a)&&group.count(b))
                return false;
        }
        return true;
    }
    
    bool dfs(unordered_set<int>& one, unordered_set<int>& two, vector<vector<int>>& dislikes){
        for(auto it = two.begin(); it!=two.end(); it++){
            bool a = false;
            
            one.insert(*it);
            two.erase(*it);
            if(isValid(one, dislikes)&&isValid(two, dislikes)){
                return true;
            }else if(isValid(one, dislikes)&&!isValid(two, dislikes)){
                a = dfs(one, two, dislikes);
            }else {
                one.erase(*it);
                two.insert(*it);
            }
            if(a){
                return true;
            }   
        }
        return false;  
    }
    bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
        unordered_set<int> one, two;
        for(int i = 1; i<=N; i++){
            two.insert(i);
        }
        bool res = dfs(one, two, dislikes);
        return res;
    }
};
2

这是对应哪里？ 你给张截图？

3

不是对应代码的 是runtime error造成的 所以现实line 345:char 35 代码就写了41行。
https://paste.ubuntu.com/p/WtSv9tPhqD/

4

你这哪里用到hashtable了？

参考一下这个

5

c++的unordered_set底层是用hash map实现的 我没有用hash map

6

set 改成 long试试？

7

也还是不行 应该是iterator的问题 因为我在for循环中是用iterator来遍历的 删了一个数字后这个set的iterator可能变了 老师会不会是这个问题 我后面把set变成了vector以后提交就是超时了 不再是runtime error。 所以老师我这个算法应该是对的把

8

iterator遍历的时候是不能修改的

9

嗯嗯 是这个原因

10

贴一下ac的代码吧 还是要练练一道dfs的题目卡了 没有一次写成功

class Solution {
public:
    bool isValid(unordered_map<int,vector<int>>& graph, int color, int cur, vector<int>& colors){
        if(colors[cur]!= 0){
            return colors[cur] == color;
        }

        colors[cur] = color;
        for(int node:graph[cur]){
            if(!isValid(graph, -1*color, node, colors))
                return false;
        }
        return true;
    }
    
    bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
        vector<int> colors(N+1,0);
        unordered_map<int,vector<int>> graph;
        for(int i = 0; i<dislikes.size(); i++){
            int a = dislikes[i][0];
            int b = dislikes[i][1];
            graph[a].push_back(b);
            graph[b].push_back(a);
            
        }
        for(int i = 1; i<=N ; i++){
            if(colors[i] == 0&&!isValid(graph,1,i,colors))
                return false;
        }
        return true;
    }
};