/////////////////////////////////////////////////////////////////// graph.h
#ifndef GRAPH_H
#define GRAPH_H

#include <map>
#include <vector>
#include <algorithm>

bool compare(const std::pair<int, int> &a, const std::pair<int, int> &b)
{
    return a.second < b.second;
}


template<typename T>
class Graph
{
public:

    class Node
    {
    public:

        T data;

        Node(const T &data = T()) : data(data)
        {}


    };

    ~Graph()
    {
        for (Node *node : _nodes)
            delete node;
    }

    Node *addNode(const T &data = T())
    {
        Node *node = new Node(data);

        _nodes.push_back(node);

        return node;
    }

    void addEdge(Node *nodeSource, Node *nodeDest)
    {
        bool existsNodeSource = std::find(_nodes.begin(), _nodes.end(), nodeSource) != _nodes.end();
        bool existsNodeDest = std::find(_nodes.begin(), _nodes.end(), nodeDest) != _nodes.end();

        if (existsNodeSource && existsNodeDest)
            _adjList.insert({nodeSource, nodeDest});
    }

    bool doesFollow(Node *nodeX, Node *nodeY)
    {
        auto res = _adjList.equal_range(nodeX);
        for (auto it = res.first; it != res.second; ++it)
        {
            Node *check = it->second;
            if (check->data == nodeY->data)
                return true;
        }
        return false;
    }

    std::vector<T> followers(Node *nodeX)
    {
        std::vector<T> followers;
        auto res = _adjList.equal_range(nodeX);
        for (auto it = res.first; it != res.second; ++it)
        {
            Node *check = it->second;
            followers.push_back(check->data);
        }

        return followers;
    }

    T findTheStalker()
    {
     return   findBySubs(true);
    }

    T findTheMostPopular()
    {

        return findBySubs(false);
    }

    T findBySubs(bool byFollowers)
    {
        std::map<Node *, size_t> subscriptions;
        for (auto it = _adjList.begin(); it != _adjList.end(); ++it)
        {
            Node *check;
            if (byFollowers)
                check = it->first;
            else
                check = it->second;
            subscriptions[check] += 1;
        }


        int max = -1;
        Node *max_user;
        for (auto it = subscriptions.begin(); it != subscriptions.end(); ++it)
        {
            if ((int) it->second > max)
            {
                max = it->second;
                max_user = it->first;
            }
        }

        return max_user->data;
    }

private:

    std::multimap<Node *, Node *> _adjList;

    std::vector<Node *> _nodes;

};

#endif




/////////////////////////////////////////////////////////////////// main.cpp

#include <iostream>
#include "graph.h"


int main()
{
    Graph<std::string> graph;

    Graph<std::string>::Node *yulian = graph.addNode("Yulian");
    Graph<std::string>::Node *anna = graph.addNode("Anna");
    Graph<std::string>::Node *michael = graph.addNode("Michael");
    Graph<std::string>::Node *john = graph.addNode("John");
    Graph<std::string>::Node *angela = graph.addNode("Angela");


    graph.addEdge(michael, anna);
    graph.addEdge(michael, yulian);
    graph.addEdge(yulian, michael);
    graph.addEdge(yulian, anna);
    graph.addEdge(john, michael);
    graph.addEdge(john, yulian);
    graph.addEdge(john, anna);
    graph.addEdge(john, angela);
    graph.addEdge(angela, anna);


    std::cout << graph.doesFollow(yulian, anna) << '\n';
    std::cout << graph.doesFollow(yulian, angela) << '\n';
    std::cout << graph.doesFollow(angela, michael) << '\n';
    std::cout << graph.doesFollow(john, michael) << '\n';
    std::cout << graph.doesFollow(michael, michael) << '\n';

    std::vector<std::string> followers = graph.followers(anna);
    for (const std::string &follower:followers)
        std::cout << anna->data << ": " << follower << '\n';


    followers = graph.followers(john);
    for (const std::string &follower:followers)
        std::cout << john->data << ": " << follower << '\n';

    std::cout << "Most subscriptions: " << graph.findTheStalker() << '\n';
    std::cout << "Most subscribers: " << graph.findTheMostPopular() << '\n';

    return 0;
}