生成树
生成树
https://ac.nowcoder.com/acm/problem/20807
题目
有一张 个点的完全图(即任意两点之间都有无向边)
现在给出这张图的两棵生成树
定义一次操作为:在任意一棵生成树中删除一条边后再加入一条边(必须在同一棵树中操作),同时需要保证操作完后仍然是一棵树。
问使得两棵树相同的最少操作次数,若不存在合法的操作方案,输出-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; }