#include <vector>
#include "spioni.h"
#define DEGEN 6
#define KAND 5
using namespace std;

/* Počet špíónů */
static int n;

struct spion
{
  vector<int> zna;		/* Seznam známých špiónů */
  vector<int> zamnou;		/* Seznam těch, co jsou za mnou */
  int kand;			/* Aktuálně volený kandidát */
  int pred_pro_kand[KAND];  /* Počet špiónů přede mnou, volících daného kandidáta */

  spion(void) : zna(), zamnou(), kand(0)
    {
      int i;
      for (i = 0; i < KAND; i++)
	pred_pro_kand[i] = 0;
    }
};

/* Seznam špiónů */
static vector<spion> sezsp;

/* Počet bodů pro daného kandidáta */
static int bodu[KAND];

/* Nalezne pořadí takové, aby každý znal nanejvýš DEGEN špíónů za ním */
static void urci_poradi()
{
  bool odebran[n];		/* Zda už byl špión odebrán */
  int znamych[n];		/* Počet zbývajících známých */
  vector<int> malo;		/* Seznam špiónů s nanevýš DEGEN známými */
  int i;

  for (i = 0; i < n; i++)
    {
      odebran[i] = false;
      znamych[i] = sezsp[i].zna.size();
      if (znamych[i] <= DEGEN)
	malo.push_back(i);
    }

  while (!malo.empty())
    {
      int aktualni = malo.back();
      malo.pop_back();

      odebran[aktualni] = true;
      vector<int>::iterator s = sezsp[aktualni].zna.begin();
      vector<int>::iterator se = sezsp[aktualni].zna.end();
      for (; s < se; ++s)
	if (!odebran[*s])
	  {
	    sezsp[aktualni].zamnou.push_back(*s);
	    znamych[*s]--;
	    if (znamych[*s] == DEGEN)
	      malo.push_back(*s);
	  }
    }
}

static void inicializuj_pocty()
{
  int s;
  vector <int>::iterator sous;

  for (s = 0; s < n; s++)
    for (sous = sezsp[s].zamnou.begin(); sous != sezsp[s].zamnou.end(); ++sous)
      sezsp[*sous].pred_pro_kand[sezsp[s].kand]++;

  for (s = 0; s < n; s++)
    bodu[sezsp[s].kand] += sezsp[s].pred_pro_kand[sezsp[s].kand];
}

void spioni(int inpn, int m, int znaji_se[][2], int voli[])
{
  int i;

  n = inpn;
  sezsp.resize(n + 1);
  for (i = 0; i < n; i++)
    sezsp[i].kand = voli[i];
  for (i = 0; i < m; i++)
    {
      int s1 = znaji_se[i][0];
      int s2 = znaji_se[i][1];
      sezsp[s1].zna.push_back(s2);
      sezsp[s2].zna.push_back(s1);
    }
  urci_poradi();
  inicializuj_pocty();
}

void zmen_nazor(int spion, int voli)
{
  int puvodni = sezsp[spion].kand;
  int pro_puv = 0, pro_nov = 0;
  vector<int>::iterator sous;

  if (puvodni == voli)
    return;
  sezsp[spion].kand = voli;

  for (sous = sezsp[spion].zamnou.begin(); sous != sezsp[spion].zamnou.end(); ++sous)
    {
      int skand = sezsp[*sous].kand;

      if (skand == puvodni)
	pro_puv++;
      else if (skand == voli)
	pro_nov++;

      sezsp[*sous].pred_pro_kand[puvodni]--;
      sezsp[*sous].pred_pro_kand[voli]++;
    }

  bodu[puvodni] -= sezsp[spion].pred_pro_kand[puvodni] + pro_puv;
  bodu[voli] += sezsp[spion].pred_pro_kand[voli] + pro_nov;
}

void pocet_bodu(int pocet[KAND])
{
  int i;
  for (i = 0; i < KAND; i++)
    pocet[i] = bodu[i];
}