Задача "K-Harmonious group"

#include <cstdio>
#include <string>
#include <set>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;

int debug = 0; // установите в 1 для вывода отладочной 
               // информации 
#define M 20002
#define MP make_pair

vector< map<int,int > > adj;  /* adj - "матрица смежности" */
vector< map<int,int > > adj2; /* Копия adj */

map<string,int> id;   /* Отображение name->id */
map<int,string> name; /* Отображение id->name */

/* Множество пар (степень вершины, вершина)
 * set используется как очередь с приоритетами
 * Ключ - степень вершины, значение - идентификатор вершины
 */
set< pair<int,int> > q;
set< pair<int,int> > q2; // копия q для второго прохода

int m, n = 0;
int petr = 0;
string petr_name("Petr");

/* Возвращает целочисленный идентификатор вершины по её имени.
 * Если вершина новая, то добавляет её в словари name и id.
 * Хранилище строк с идентификаторами называется string pool 
 * или quark (см. Glib - http://library.gnome.org/devel/glib/stable/glib-data-types.html).
 */
int getid(string s) {
   if( id.find(s) == id.end() ) {
        // если имени нет в словаре, то добавим его туда,
        // назначив ему следующий порядковый идентификатор
        id[s] = n;
        name[n] = s;
        return n++;
    } else {
        // иначе вернем идентификатор человека с таким именем
        return id[s];
    }
}
/* По идентификатору строки находит саму строку 
 * (в данной задаче не используется)
 */
string getname(int id) {
  return name[id];
}

int main( ) {
    scanf("%d", &m); // считываем число рёбер 

    adj.resize(2 * m); // число вершин не более чем 2 * m
    for ( int i = 0 ; i < m ; i++ ) {
        char s[50],d[50]; // имена вершин (source,destination)
        string ss, dd;    // их string-овый вариант
        int s_id, d_id;   // и их целочисленные идентификаторы
        scanf("%s%s", s, d);
        ss = s;  // В этих строчках происходит копирование 
                 // содержания строк, а не их адресов.
        dd = d;  // Дело в том, что оператор присвоения (=) 
                 // переопределён для случая, 
                 // когда справа стоит char*, а слева string.

        s_id = getid(ss);
        d_id = getid(dd);

        if ( adj[s_id].find(d_id) != adj[s_id].end() ) {
            fprintf(stderr, "Duplicate: %s %s\n", s, d);
        }
        if ( s_id == d_id ) {
            fprintf(stderr, "Equal     : %s %s\n", s, d);
        }
        adj[d_id][s_id] = 1;
        adj[s_id][d_id] = 1;
    }

    petr = getid(petr_name);

    for ( int i = 0 ; i < n ; i++ ) {
        q.insert( MP(adj[i].size(), i) );
    }

    q2 = q;     // Создадим копии для второго прохода
    adj2 = adj; //   

    int max_degree = (*(q.begin())).first;
    int degree, a;
    while ( q.size() ) {
        /* извлекаем  вершину с минимальной степенью ("слабое 
       звено" - работник, у которого меньше всего друзей) */
        degree = (*(q.begin())).first;
        a      = (*(q.begin())).second;
        /* Дело в том, что set.first() возвращает _наименьшую_
       пару. Порядок на парах, совпадает с порядком на первом
       элементе. Первый элемент нашей пары - степень вершины. 
        Таким образом, set может использоваться для реализации 
        функциональности очереди с приоритетом.*/
        if ( debug ) 
            printf("Max degree=%d\nExtracting %s with %d\n\n", 
                       max_degree, name[a].c_str(), degree);

        if ( max_degree < degree ) {
            max_degree = degree;
        }
        if ( a == petr ) break;

        // удаляем "слабое звено"
        q.erase(q.begin());

        // и "подчищаем" все его "дружбы"
        map<int, int> friends = adj[a];
        map<int,int>::iterator it;
        for(it = friends.begin();it != friends.end();it++) {
            int b = (*it).first;
            q.erase( MP(adj[b].size(), b ) );
            adj[b].erase(a);
            q.insert( MP(adj[b].size(), b) );
        }
    }

    if (debug) {printf("Final max degree=%d\n", max_degree);}
    
    /* Итак, мы узнали  максимальное значение "стабильности".
      Теперь повторим все сначала, уже печатая ответ.  */
    while ( q2.size() ) {
        degree = (*(q2.begin())).first;
        a      = (*(q2.begin())).second;
        if ( degree >= max_degree ) {
            break;
        }
        q2.erase( q2.begin() );
        if ( debug ) 
           printf("Max degree=%d\nExtracting %s with %d\n\n",
                   max_degree, name[a].c_str(), degree);

        map<int,int> friends = adj2[a];
        map<int,int>::iterator it;
        for (it = friends.begin();it != friends.end();it++) {
            int b = (*it).first;
            q2.erase( MP(adj2[b].size(), b ) );
            adj2[b].erase(a);
            q2.insert( MP(adj2[b].size(), b) );
        }
    }
    // Выводим размер коллектива и его стабильность
    printf("%d %d\n", q2.size(), max_degree);
    set<string> answer; // шаблон set можно использовать 
                        // для сортировки;
    {
        set< pair<int,int> >::iterator j;
        for ( j = q2.begin(); j != q2.end() ; j++ ) {
            answer.insert( name[((*j).second)]  );
        }
    }
    {
        set<string>::iterator j;
        for ( j = answer.begin(); j != answer.end() ; j++ ) {
            printf("%s ", (*j).c_str() );
        }
    }
    printf("\n");
    return 0;
}