leetcode1466

发布时间 2023-09-15 15:04:45作者: iu本u

分析:

  • 它是有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;
}