68ms in C++ by Union Find and BFS


  • 0
    R

    Background:

    1. use a vector to save the possible node set. Firstly initialize the vector by the first edge pair.

    2. set up a deque which is initialized by the elements of edges from index i to the last one.

    3. in every loop, use deque.size() as the termination condition in order to traverse every elements of deque.

    4. if either element in deque.front() is found in any set, add it
      if not, pop edque.front() out and push it back to the tail of deque

       class Solution {
       public:
           int countComponents(int n, vector<pair<int, int>>& edges) {
               if(edges.empty()||n==0) return n;
               deque<pair<int,int>> deq;
               vector<set<int>> res = {{edges[0].first, edges[0].second}};   //the node set
               int pn = 2;   //the number of recorded node
               for(int i=1;i<=edges.size()-1;++i)
                   deq.push_back(edges[i]);
           
               while(!deq.empty()){
                   bool insert_big = false;  //to point out if there is no insertion in the whole traverse
                   int sz = deq.size();   //termination condition
                   while(sz!=0){
                       int u = deq.front().first;
                       int v = deq.front().second;
                       bool insert_sml = false;
                       --sz;
                      for(int j=0;j<=res.size()-1;++j){
                          set<int>& s_tp = res[j];
                          if(s_tp.find(u)!=s_tp.end()&&s_tp.find(v)!=s_tp.end()){
                                deq.pop_front();
                                insert_sml = true;
                                insert_big = true;
                                break;
                           }
                          else if(s_tp.find(u)!=s_tp.end()||s_tp.find(v)!=s_tp.end()){
                                if(s_tp.find(u)!=s_tp.end()) s_tp.insert(v);
                                if(s_tp.find(v)!=s_tp.end()) s_tp.insert(u);
                                ++pn;
                                deq.pop_front();
                                insert_sml = true;
                                insert_big = true;
                                break;
                          }
                     }
                   if(!insert_sml){
                       pair<int,int> cur = deq.front();
                       deq.pop_front();
                       deq.push_back(cur);
                   }
               }
               if(!insert_big){
                       int u = deq.front().first;
                       int v = deq.front().second;
                       res.push_back({u,v});
                       pn = pn+2;
                       deq.pop_front();
                   }
           }
           return n-pn+res.size();
           }
        };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.