生成树

题目

有一张 个点的完全图（即任意两点之间都有无向边）
现在给出这张图的两棵生成树
定义一次操作为：在任意一棵生成树中删除一条边后再加入一条边（必须在同一棵树中操作），同时需要保证操作完后仍然是一棵树。
问使得两棵树相同的最少操作次数，若不存在合法的操作方案，输出-1

注意：这里的相同指的是点集与边集均相同，也就是对于第一棵树中的边 ，第二棵树中一定存在边 或 。

解题思路

可以使用集合 数据结构 记录第一棵树的边。
再遍历第二棵树的边，若 这条边不在第一棵树中，则需要进行一次操作，累加计入结果 中。

C++代码

#include<iostream>
#include<set>
using namespace std;

int main(){
    int n;
    cin >> n;
    set<pair<int,int>> st;
    int u, v;
    for(int i=0; i<n-1; ++i){
        cin >> u >> v;
        st.insert(make_pair(u,v));
        st.insert(make_pair(v,u));
    }

    int cnt = 0;
    for(int i=0; i<n-1; ++i){
        cin >> u >> v;
        if(st.count(make_pair(u,v)) <= 0)
            ++cnt;
    }
    cout << cnt << endl;
    return 0;
}