#include <stdio.h>
#include <stdlib.h>

struct task
{
    int runtime;
    int id1;
    int id2;
};//structure to store the running time and the dependancies of each of the tasks

int x = 0;//global counter for the indices of the task index array
int y = 0;//global counter for the indices of the dependant tasks

void check(struct task *arr, int a, int *ind)//recursive funtion to find all the tasks on which a given task depends
{
    if (arr[a - 1].id1 == -1 && arr[a - 1].id2 == -1)//base case when it doesn't depend on any task
    {
        return;
    }

    if (arr[a - 1].id1 != -1)
    {
        ind[x] = arr[a - 1].id1;//update the ind array in case of a dependancy is found in the first id(id1)
        x++;
        check(arr, arr[a - 1].id1, ind);//recursive call to the id1 to check for further dependancies of id1
    }

    if (arr[a - 1].id2 != -1)
    {
        ind[x] = arr[a - 1].id2;//update the ind array in case of a dependancy is found in the second id(id2)
        x++;
        check(arr, arr[a - 1].id2, ind);//recursive call to the id1 to check for further dependancies of id2
    }
}

void check_dependant(struct task *arr, int n, int a, int *dependant)//function to find the tasks that are dependant on a given task
{
    for (int i = 0; i < n; i++)//iterate over the array of struct task to find if any task is dependant on a given task "a"
    {
        if (arr[i].id1 == a || arr[i].id2 == a)
        {
            dependant[y] = i;//if a dependant task is found then update the dependant array and increment value of y
            y++;
        }
    }

    return;
}

int make_unique(int *ind, int *temp, int x)// function to make the dependancy array ie. "ind" unique ( one task appears only once)
{
    static int count = 0;//static variable to keep count
    for (int i = 0; i < x; i++)
    {
        int j;
        for (j = 0; j < count; j++)
        {
            if (ind[i] == temp[j])// if a common element is found then break there and then move ahead for further checks
                break;
        }
        if (j == count)
        {
            temp[count] = ind[i];//store the unique elements in the temp array
            count++;
        }
    }

    return count;// return the size of the unique array - temp
}

int main(int argc, char const *argv[])
{
    int n; //the number of tasks
    printf("Enter the number of tasks to perform: ");
    scanf("%d", &n); //user input for the number of tasks

    struct task *arr = (struct task *)malloc(n * sizeof(struct task)); //dynamically create an array of struct task type for n inputs

    for (int i = 0; i < n; i++)//user input the details of the tasks
    {
        scanf("%d", &arr[i].runtime);
        scanf("%d", &arr[i].id1);
        scanf("%d", &arr[i].id2);
    }

    int total_time = 0;
    //loop over all the tasks to find the total running time of all the tasks
    for (int i = 0; i < n; i++)
    {
        total_time += arr[i].runtime;// summing all the runtimes over all the tasks
    }
    printf("Total time= %d\n\n", total_time);// printing total time taken to run the tasks

    int a;// the task number to perform further operations with
    printf("Enter the task number to search for: ");
    scanf("%d", &a); //user input for the task number a
    printf("Earliest time when T%d can start=", a);

    int *ind = (int *)malloc(n * sizeof(int));// array to store all the task numbers on which the task a is dependant
    int *temp = (int *)malloc(n * sizeof(int));// array to store unique tasks on which the task a is deoendant
    check(arr, a, ind);//calling check function to fill up the ind array
    int c = make_unique(ind, temp, x);//calling make unique function to remove the duplicates and then storing its size in c
    int min_time = 0;
    for (int i = 0; i < c; i++)
    {
        min_time += arr[temp[i] - 1].runtime;//sum of runtime of all tasks needed to be done before a
    }

    printf("%d\n\n", min_time);// printing that minimum time before the task a can be started

    int *dependant = (int *)malloc(n * sizeof(int));//dynamic allocation of the array of tasks that depend on task a
    check_dependant(arr, n, a, dependant);//find and fill the elements of dependant array

    printf("List of tasks that cannot be scheduled before T%d = ", a);
    //special cases
    if (y == 1)
    {
        printf("{T%d}", dependant[0]+1);
    }
    else if (y == 0)
    {
        printf("NONE");
    }
    else//general case
    {
        for (int i = 0; i < y; i++)//printing the dependant array
        {
            if (i == 0)
            {
                printf("{T%d, ", dependant[i] + 1);
            }
            else if (i == y - 1)
            {
                printf("T%d}", dependant[i] + 1);
            }
            else
            {
                printf("T%d, ", dependant[i] + 1);
            }
        }
    }

    return 0;
}