11440 - DS_hw4   

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”.
 

    1. 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.

    2.  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.

    3. void deleteVertex(const int label);

Delete the vertex label and all edges connected to label.
Iflabel doesn't exist in this graph, do nothing.

    4. int degree(const int label);

Return the degree of vertex label.
Iflabel doesn't exist in this graph, return 0.

     5. int weight(const int label); 

Return the sum of edge weight of vertex label.
Iflabel doesn't exist in this graph, return 0.

    6. 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.

    7. void deleteGraph();
       Delete all vertices and edges in the graph.

    8. 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.

Input

The input is several instructions.

Output

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

Sample Input  Download

Sample Output  Download

Partial Judge Code

11440.cpp

Partial Judge Header

11440.h

Tags

Cube Cuboid(a, a, a)



Discuss