“used without template parameters”

VisitedSet is a template, not a class, so you can’t use VisitedSet in a nested name specifier such as VisitedSet::getSize(). Just as you specified the declaration of class VisitedSet<T> for all class T, you must specify the definition of VisitedSet<T>::getSize() for all class T:

template<class T>
int VisitedSet<T>::getSize() {
//            ^^^
    return vec.size();
}

The name of a template can, however, be used as though it were a class within a template definition:

template<class T>
struct Example {
    Example* parent;
    T x, y;
};

In this case, Example is short for Example<T>.