给定两个 图 G1和G2，任务是找到两个给定图的并集和交集，即(G1 ∪ G2)和(G1 ∩ G2)。

例子：

输入：G1 = { (“e1”, 1, 2), (“e2”, 1, 3), (“e3”, 3, 4), (“e4”, 2, 4) }, G2 = = { (“e4”, 2, 4), (“e5”, 2, 5), (“e6”, 4, 5) }输出：G1 接头 G2 ise1 1 2e2 1 3e3 3 4e4 2 4e5 2 5e6 4 5

G1 交点 G2 ise4 2 4 解释：图 G1 和 G2 的并集：

图 G1 和 G2 的交集：

方法：按照以下步骤解决问题：

• 定义一个函数，例如 Union(G1, G2)，以求 G1 和 G2 的并集：
  • 初始化一个 map，比如添加，存储是否已添加边。
  • 遍历图 G1 的边，并推入图中的所有边，比如 G，并将所有访问过的边标记为已添加。
  • 现在，再次遍历图 G2 的边，如果尚未添加边，则将边推入 G 中，然后在添加的地图中标记添加的边。
• 定义一个函数说 Intersection(G1, G2) 来找到 G1 和 G2 的交点：
  • 初始化一个 map，比如 added ，用于存储是否已添加边。
  • 遍历图 G1 的边，并标记添加的地图中访问过的所有边。
  • 现在，再次遍历图 G2 的边，并在图 G 中推边(如果已添加边)。然后，标记地图中添加的边。
• 现在，打印 Union(G1, G2) 和 Intersection(G1, G2) 函数调用后得到的图形。

下面是上述方法的实现：

C++ 14

// C++ program for the above approach

#include <bits/stdc++.h>

using namespace std;

  // Function to find union of two graphs

void find_union(

    vector<tuple<string, int, int> > G1,

    vector<tuple<string, int, int> > G2)

{

    // Stores an edge of the graph G1

    map<string, pair<int, int> > added;

      // Stores the unioun graph G1

    vector<tuple<string, int, int> > G;

      // Iterate over the edges

    // of the graph G1

    for (auto p : G1) {

          string a = get<0>(p);

          // Get the edges

        int b = get<1>(p);

        int c = get<2>(p);

          // Insert the current

        // edges into graph G

        G.push_back(

            make_tuple(a, b, c));

        added[a] = { b, c };

    }

      // Iterate over the edges

    // of the graph G1

    for (auto p : G2) {

          string a = get<0>(p);

        int b = get<1>(p);

        int c = get<2>(p);

          pair<int, int> x = { b, c };

        pair<int, int> y = { c, b };

          // If either edge x or

        // y is already added

        if (added[a] == x || added[a] == y)

            continue;

          // Otherwise

        G.push_back(make_tuple(a, b, c));

    }

      // Print the unioun

    cout << "G1 union G2 is

";

      for (auto p : G) {

          string a = get<0>(p);

        int b = get<1>(p);

        int c = get<2>(p);

        cout << a << " " << b << " "

             << c << endl;

    }

}

  // Function to find intersection of two graphs

void find_intersection(

    vector<tuple<string, int, int> > G1,

    vector<tuple<string, int, int> > G2)

{

    // Stores an edge

    map<string, pair<int, int> > added;

      // Stores the graph of intersection

    vector<tuple<string, int, int> > G;

      // Iterate over edges of graph G1

    for (auto p : G1) {

        string a = get<0>(p);

        int b = get<1>(p);

        int c = get<2>(p);

          added[a] = { b, c };

    }

      // Iterate over edges of graph G2

    for (auto p : G2) {

          string a = get<0>(p);

        int b = get<1>(p);

        int c = get<2>(p);

          pair<int, int> x = { b, c };

        pair<int, int> y = { c, b };

          // If either edge x or

        // y is already added

        if (added[a] == x || added[a] == y)

            G.push_back(make_tuple(a, b, c));

    }

      // Print the graph G

    cout << "G1 intersection G2 is

";

      for (auto p : G) {

          string a = get<0>(p);

        int b = get<1>(p);

        int c = get<2>(p);

          cout << a << " " << b

             << " " << c << endl;

    }

}

  // Driver Code

int main()

{

    vector<tuple<string, int, int> > G1

        = { make_tuple("e1", 1, 2),

            make_tuple("e2", 1, 3),

            make_tuple("e3", 3, 4),

            make_tuple("e4", 2, 4) };

      vector<tuple<string, int, int> > G2

        = { make_tuple("e4", 2, 4),

            make_tuple("e5", 2, 5),

            make_tuple("e6", 4, 5) };

      // Function call for finding the

    // Union of the given graph

    find_union(G1, G2);

      // Function call for finding the

    // Intersection of the given graph

    find_intersection(G1, G2);

      return 0;

}

G1 union G2 is

e1 1 2

e2 1 3

e3 3 4

e4 2 4

e5 2 5

e6 4 5

G1 intersection G2 is

e4 2 4

时间复杂度：O(N * log(N))空间复杂度：O(N)