$30.00

## Description

Description

Please construct a simple undirected graph (each node contains a 32bit signed integer) with 8 functions: “addEdge”, “deleteEdge”, “deleteVertex”, “degree”, “weight”, “isExistPath”,” deleteGraph” and “number_of_component”.

**void****addEdge(****const int****label_1,****const int****label_2 ,****const int****weight);**

A function can add an edge between vertex label_1 & label_2 with edge weight = weight.

If vertex label_1 or label_2 doesn’t exist in the graph, create vertex label_1 or label_2 in this graph.

Please note that the edge weight should be the weight that this edge was first added into graph.

e.g. addEdge 0 5 3

addEdge 5 0 10

Then the edge weight of edge 05 is 3.

**void****deleteEdge(****const int****label_1,****const int****label_2);**

Delete the edge between vertex label_1 & label_2.

If this edge doesn’t exist in this graph, do nothing.

**void****deleteVertex(****const int****label);**

Delete the vertex label and all edges connected to label.

If label doesn’t exist in this graph, do nothing.

**int****degree(****const int****label);**

Return the degree of vertex label.

If label doesn’t exist in this graph, return 0.

**int****weight(****const int****label);**

Return the sum of edge weight of vertex label.

If label doesn’t exist in this graph, return 0.

**bool****isExistPath(****const int****label_1,****const int****label_2);**If there is at least one path between label_1 & label_2, return true.

If there’s no path between label_1 & label_2 or at least one of label_1 and label_2 doesn’t exist in the graph, return false.**void****deleteGraph();**Delete all vertices and edges in the graph.

**int****number_of_component();**

Return the number of the components in this graph.

If there’s no vertex in this graph, return 0.

Implement these functions in **function.cpp.**

Note

Each of the 3 hidden test cases contains up to 300,000 instructions and each graph may have 150,000 of nodes.

The time limit for test cases 1-3 are 1 sec, time limit for test case 4 is 20 sec.

You have to **#include “function.h”** to include the partial judge header that we provided.

The testing case1 is similar to Sample Input and make sure your code can pass basic testing to get 60.

題目: __http://acm.cs.nthu.edu.tw/problem/11440/__

Upload your function.cpp as [studentID]_hw4.zip and submit to ilms BEFORE the deadline.

Input

**The input is several instructions:**

addEdge 4 6 8

addEdge 7 9 5

addEdge 6 8 4

addEdge 0 3 8

addEdge 8 9 6

weight 6

addEdge 9 5 6

deleteVertex 5

addEdge 6 8 2

weight 9

isExistPath 0 8

addEdge 2 4 6

number_of_component

Output

**If your code is correct, the output for online judge would be “[All Accepted]”.**

12

11

false

2