leetcode1466

标签：count int auto vis vec push leetcode1466

分析：

• 它是有n个节点，n-1条边
• 所以两个节点连接的边只有一条，那么要么是可以从这条边的起点开始能够到达0，要么是不能，不会有回路的情况
• 对于数据结构使用哈希表值为vector容器

int bfs(vector<vector<int>>& connections){
    unordered_map<int,vector<int>>m;
    for(auto& v:connections){
        m[v[0]].push_back(v);
        m[v[1]].push_back(v);
    }
    set<int>vis;//集合数据不能重复
    queue<vector<int>>q;
    for(auto& l:m[0]){
        q.push(l);//将含有端点0的边放进队列
    }
    vis.insert(0);
    while(!q.empty()){
        auto vec=q.front();q.pop();
        int u=vec[0];//所遍历边的起点
        for(auto& l:m[u]){
            if(vis.count(u)){//这个起点已经遍历过说明可以到0，那么终点就不能到0，更改方案
                ans++;
                u=vec[1];
            }
        }
        vis.insert(u);//因为更改了方向，可以到0
        for(auto& l:m[u]){
            if(vis.count(l[0])&&vis.count(l[1]))//这条边已经考虑过方案
            continue;
            q.push(l);
        }
    }
    return ans;
}

 

标签：count,int,auto,vis,vec,push,leetcode1466
From： https://www.cnblogs.com/wangkaixin-yy/p/17705035.html