War

#include <fstream>
#include <vector>
#include <set>
#include <queue>
#include <utility>


std::ifstream fin ("warcraft.in");
std::ofstream fout ("warcraft.out");

int n, m, x, cnt_conex, cnt_Frost_Wolf, cnt_total, Frost_Wolf;
std::vector <std::vector <int>> Graph;
std::vector <std::set <int>> Skills;
std::vector <bool> Warchief, Seen;
std::vector <int> Tribes;
std::queue <int> Q;
std::set <std::pair <int, std::pair <int, int>>> Store;


inline void BFS (int src)
{
    std::vector <int> Count_Sk (n + 1, 0);
    int cnt_trb = 0;
    bool OK = false;

    Q.push (src); Seen[src] = true;

    while (!Q.empty ())
    {
        int v = Q.front (); Q.pop (); ++ cnt_trb;

        if (v != src)
            for (auto sk : Skills[v])
                ++ Count_Sk[sk];

        if (v == x)
            OK = true;

        for (auto u : Graph[v])
            if (!Seen[u])
                Seen[u] = true, Q.push (u);
    }

    Tribes[src] = cnt_trb;
    if (OK)
        cnt_Frost_Wolf = cnt_trb, Frost_Wolf = src;

    ///for (auto sk : Skills[src])
        ///-- Count_Sk [sk];

    for (int sk = 1; sk <= m; ++ sk)
        if (Count_Sk[sk] == 1)
            Skills[src].insert (sk);
}


int main ()
{
    fin >> n >> m >> x;

    Graph = std::vector <std::vector <int>> (n + 1);
    Skills = std::vector <std::set <int>> (n + 1);
    Warchief = Seen = std::vector <bool> (n + 1, false);
    Tribes = std::vector <int> (n + 1, 0);

    for (int i = 1, u, v, k; i <= n; ++ i)
    {
        fin >> u >> v >> k;

        if (v)
            Graph[v].push_back (u);
        else
            Warchief[u] = true;

        for (int j = 1, sk; j <= k; ++ j)
        {
            fin >> sk;
            Skills[u].insert (sk);
        }
    }

    for (int v = 1; v <= n; ++ v)
        if (Warchief[v])
            ++ cnt_conex, BFS (v);

    for (int v = 1; v <= n; ++ v)
        if (v != Frost_Wolf && Warchief[v])
            Store.insert (std::make_pair (Tribes[v], std::make_pair (static_cast <int> (Skills[v].size ()), v)));

    for (auto it : Store)
    {
        if ((Tribes[Frost_Wolf] > it.first) ||
            (Tribes[Frost_Wolf] == it.first && static_cast <int> (Skills[Frost_Wolf].size ()) > it.second.first))
        {
            for (auto sk : Skills[it.second.second])
                Skills[Frost_Wolf].insert (sk);

            Tribes[Frost_Wolf] += it.first;
            Graph[Frost_Wolf].push_back (it.second.second);
        }
    }
    cnt_total = Tribes[Frost_Wolf];

    fout << cnt_conex << "\n" << cnt_Frost_Wolf << "\n" << cnt_total;

    fin.close (), fout.close ();
    return 0;
}