#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_set>
using namespace std;
/*
N = Number of Nodes
M = Number of Volunteers
F = Represents the Graph (F[i] = parent of node i)
S = M arrays, each one representing the Volunteer's record
*/
/*When you wake up tomorrow:
Insert printsets for debugging and check final iteration
*/
void printSet(const unordered_set<int>& uset) {
cout << "\tCurrent Unordered Set:\n\t";
for (int elem : uset) {
cout << elem << " ";
}
cout << "\n";
}
void dfs(int start, vector<bool> &visited, vector<vector<int> > &children, int &ctr){
//adjacency list not needed because children is the adjacency list LOL
if(visited[start] == true){
return;
}
visited[start] = true;
for(int neighbours: children[start]){
if(!visited[neighbours]){
children[start].push_back(neighbours);
//keep track of number of
ctr++;
dfs(neighbours, visited, children, ctr);
}
}
}
//each item in the vector represents the NUMBER OF CHILDREN THAT NODE HAS
int solve(int N, int M, vector<int> F, vector<vector<int> > S){
//cout << F[0] << " " << S[0][0] << "\n";
/*Generate adjacency list*/
vector<vector<int> > children(N);
for(int i = 1; i<N; i++){
children[F[i]].push_back(i);
}
//PRINT OUT ALL CHILDREN
int answer = 0;
int ctr = 0;
unordered_set<int> anticipated;
vector<int> counters(N+5, 0);
vector<bool> visited(N+5, false);
for(int i = 0; i<N-1; i++){
//cout << "ITERATION " << i << ": \n";
for(int j = 0; j<M; j++){
//cout << "\tChecking element " << S[j][i] << "..\n";
//cout << "---\n";
anticipated.insert(S[j][i]);
/*cout << "\n---\tCOUNTERS LIST: \n";
for(int i = 0; i<N; i++){
cout << counters[i] << " ";
}
cout << "\n---\tVISITED LIST: \n";
for(int i = 0; i<N; i++){
cout << visited[i] << " ";
}*/
//cout << "\t* ADDING: " << S[j][i] << "\n";
//printSet(anticipated);
int element = S[j][i];
//
if(visited[element] == false){
//cout << "\t1. This element has not been visited yet, but has already been MARKED OTHERWISE with +1\n";
visited[element] = true;
counters[element]++;
dfs(element, visited, children, ctr);
//i forgot DFS was a thing and tried doing an iterative thing :penchickdead:
/*for(int k = 0; k<children[element].size(); k++){
//children[element][k] = within a specific element, kth index across iteration
int child = children[element][k];
anticipated.insert(child);
if(visited[child] == false){
//make sure the
cout << "\t2." << k+1 << " The child, " << children[element][k] << ", hasn't been visited and has already been MARKED OTHERWISE with +1.\n";
visited[child] = true;
}
else{
cout << "\t2." << k+1 << " The child, " << children[element][k] << ", has been visited already and is ignored.\n";
}
}*/
}
else{
counters[element]++;
}
if(counters[element] >= M){
//cout << "\t!!!. ELEMENT HAS REACHED MAX COUNT, TO BE ERASED IN SET...\n";
anticipated.erase(element);
}
}
if(anticipated.size() == 0){
//cout << "\t!!!. A DAY HAS BEEN COMPLETED, RESETTING...\n";
answer++;
anticipated.clear();
counters.assign(N+5, false);
}
}
//anticipate and un-ancitipate
//perform DFS for children
return answer;
}
/*int main(){
//delete when done
int N, M;
cin >> N >> M;
vector<int> F;
vector<vector<int> > S(M, vector<int>(N-1));
for(int i = 0; i<=N-1; i++){
int x;
cin >> x;
F.push_back(x);
}
for(int i = 0; i<M; i++){
for(int j = 0; j<N-1; j++){
int x;
cin >> x;
S[i][j] = x;
}
}
cout << "\n";
for(int i = 0; i<M; i++){
for(int j = 0; j<N-1; j++){
cout << S[i][j] << " ";
}
cout << "\n";
}
cout << solve(N, M, F, S);
}*/
