#include <map>
#include <set>
#include <list>

using namespace std;

bool dfs_hasCycles(int v, int parent, set<int>& visited, const map<int,list<int> >& adjMap) { 
  bool result = false;
  visited.insert(v);

  list<int> nbrList = adjMap.find(v)->second;

  for (list<int>::iterator nbr = nbrList.begin(); nbr != nbrList.end(); nbr++){
    if ( visited.count(*nbr) == 0 ){
      result = result || dfs_hasCycles(*nbr, v, visited, adjMap);
    }else if(*nbr != parent){
      // we've visited this node, but it's not our parent, i.e. where we just came from
      result = true;
    }// else it's the parent
  }
  
  return result; 
} 

bool grop_hasCycles(const map<int, list<int> >& adjMap) { 
  set<int> visited; 

  for (map<int,list<int> >::const_iterator miter = adjMap.begin(); 
       miter != adjMap.end(); 
       miter++){ 
    int v = miter->first;
    
    if (visited.count(v) == 0 ) { 
      if (dfs_hasCycles(v, -1, visited, adjMap)){
	return true; 
      }
    } 
  } 

  return false; 
}







void dfs(int v, set<int>& visited, const map<int, list<int> >& adjMap){
  visited.insert(v);
  list<int> nbrList = adjMap.find(v)->second;
  
  list<int>::iterator nbr; 
  
  for (nbr = nbrList.begin(); nbr != nbrList.end(); nbr++){
    if (visited.count(*nbr) == 0){ 
      dfs(*nbr, visited, adjMap);
    }
  }
}

bool grop_isConnected(const map<int, list<int> >& adjMap){
  set<int> visited;
  dfs(adjMap.begin()->first, visited, adjMap);

  bool connected = true;

  for(map<int, list<int> >::const_iterator it = adjMap.begin();
      it != adjMap.end();
      it++ ){
    if( visited.count(it->first) == 0 ){
      connected = false;
    }
  }

  return connected;
}