leetcode1319 联通网络的操作次数

思路:深搜求联通分量数

熟练了二维vector的初始化以及图的邻接表思想。

leetcode1319 联通网络的操作次数

 

 

class Solution {
public:
    int makeConnected(int n, vector<vector<int>>& connections) {
        if(connections.size()<(n-1))
        {
            return -1;
        }
        vector<int> visit(n,0);
        vector<vector<int>> edges(n);
        for(int i=0;i<connections.size();i++)
        {
            vector<int> temp=connections[i];
            edges[temp[0]].push_back(temp[1]);
            edges[temp[1]].push_back(temp[0]);
        }
        int number=0;
        for(int i=0;i<n;i++)
        {
            if(visit[i]==0)
            {
                number++;
                DFS(i,visit,edges);
            }
        }
        return number-1;
    }
    void DFS(int index,vector<int> & visit,vector<vector<int>> & edges)
    {
       visit[index]=1;
       for(int i=0;i<edges[index].size();i++)
       {
           if(visit[edges[index][i]]==0)
           {
               DFS(edges[index][i],visit,edges);
           }
       }
    }
};

 

leetcode1319 联通网络的操作次数

上一篇:uniapp 跳转指定的tab导航页面


下一篇:uniapp跳转至App Store