/*
Time limit: 1000ms
Memory limit: 256mb
---------------------Copy the following code, complete it and submit---------------------
I, <Your Full Name>, am submitting the assignment for
an individual project.
I declare that the assignment here submitted is original except for
source material explicitly acknowledged, the piece of work, or a part
of the piece of work has not been submitted for more than one purpose
(i.e. to satisfy the requirements in two different courses) without
declaration. I also acknowledge that I am aware of University policy
and regulations on honesty in academic work, and of the disciplinary
guidelines and procedures applicable to breaches of such policy and
regulations, as contained in the University website
http://www.cuhk.edu.hk/policy/academichonesty/.
It is also understood that assignments without a properly signed
declaration by the student concerned will not be graded by the
teacher(s).
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
// this linked list has no head or tail, which means that if this list is empty, then it equals NULL
struct linkedListNode {
int id;
int value;
struct linkedListNode* next;
};
typedef struct linkedListNode* ListNode;
ListNode CreateNode(int id, int value) {
ListNode node = (ListNode) malloc(sizeof(struct linkedListNode));
node->id = id;
node->value = value;
node->next = NULL;
return node;
}
// Stack ADT
struct stack {
int capacity;
int* arr;
int size;
};
typedef struct stack* StackADT;
StackADT CreateStack(int capacity) {
StackADT s = (StackADT) malloc(sizeof(struct stack));
s->arr = (int*) malloc(capacity * sizeof(int));
s->capacity = capacity;
s->size = 0;
return s;
}
int IsEmpty(StackADT s) {
return s->size == 0;
}
void Push(StackADT s, int value) {
if (s->size < s->capacity) {
s->arr[s->size++] = value;
}
}
void Pop(StackADT s) {
if (!IsEmpty(s)) {
s->size--;
}
}
int Top(StackADT s) {
return s->arr[s->size-1];
}
// graph
// We use array to maintain nodes instead of the hashTables.
// For example, G[i] is exactly the adjacency list of the node i
struct graph {
int n;
long long Forward_sum, Backward_sum, Cross_sum;
int* color;
int* discovery_time;
int* finish_time;
int time;
ListNode* G;
};
typedef struct graph* GraphADT;
GraphADT CreateGraph(int n) {
GraphADT myGraph = (GraphADT) malloc(sizeof(struct graph));
myGraph->n = n;
myGraph->Forward_sum = 0;
myGraph->Backward_sum = 0;
myGraph->Cross_sum = 0;
myGraph->time = 0;
myGraph->color = (int*) malloc(n * sizeof(int));
myGraph->discovery_time = (int*) malloc(n * sizeof(int));
myGraph->finish_time = (int*) malloc(n * sizeof(int));
myGraph->G = (ListNode*) malloc(n * sizeof(ListNode));
memset(myGraph->G, 0, n * sizeof(ListNode));
memset(myGraph->color, 0, n * sizeof(int));
memset(myGraph->discovery_time, 0, n * sizeof(int));
memset(myGraph->finish_time, 0, n * sizeof(int));
return myGraph;
}
// In our test case, each edge is only added once
void AddEdge(GraphADT myGraph, int u, int v, int w) {
// WRITE YOUR CODE HERE
}
void DFS(GraphADT myGraph, int u) {
myGraph->color[u] = 1; // Gray
myGraph->discovery_time[u] = myGraph->time++;
StackADT S = CreateStack(myGraph->n);
Push(S, u);
while(!IsEmpty(S)) {
int curr = Top(S);
// WRITE YOUR CODE HERE
}
myGraph->finish_time[u] = myGraph->time++;
}
int main()
{
int n, m;
scanf("%d", &n);
GraphADT myGraph = CreateGraph(n);
scanf("%d", &m);
for(int i=0; i<m; i++)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
AddEdge(myGraph, u, v, w);
}
for(int i=0; i<n; i++)
{
if(myGraph->color[i] == 0)
{
DFS(myGraph, i);
}
}
printf("%lld %lld %lld\n", myGraph->Forward_sum, myGraph->Backward_sum, myGraph->Cross_sum);
}
---------------------------------------End of Code---------------------------------------
## Graph ADT and DFS
Given a directed weighted graph with $n$ nodes and $m$ edges, your task is to implement a Graph Abstract Data Type (ADT) and perform a DFS traversal using an explicit stack (iterative approach) to calculate the sum of weights for Forward edges, Back edges, and Cross edges.
To ensure the traversal order is unique, we follow these rules:
- When starting a new DFS search from unvisited nodes, always pick the node with the smallest index first.
- Edge Selection: When exploring neighbors of a node, prioritize edges that appeared later in the input. (i.e., if edges $(u, v)$ and $(u, w)$ are both outgoing from $u$, and $(u, w)$ was given after $(u, v)$ in the input, visit $w$ first).
- Implementation: You must use a Stack to simulate the recursion.
### Input
The first line contains two integers $n, m (n\leq 10^5, m \leq 10^6)$, representing the number of vertices and the number of edges.
The next $m$ lines each contain three integers $u, v, w (u \neq v, 0 \leq u, v < n, |w| < 10^5 )$, representing a directed edge from $u$ to $v$ with weight $w$.
Vertices are indexed from $0$ to $n-1$.
### Output
Output three integers representing the sum of weights for Forward edges, Back edges, and Cross edges.
### Example
**Input**
4 5
0 1 10
0 2 5
1 2 2
2 0 8
2 3 1
**Output**
16 8 2
**Explanation**