本文主要是介绍蓝桥杯刷题-06-砍树-图遍历DFS⭐⭐⭐⭐，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给定一棵由 n 个结点组成的树以及 m 个不重复的无序数对 (a1, b1), (a2, b2),
. . . , (am, bm)，其中 ai 互不相同，bi 互不相同，ai ≠ bj(1 ≤ i, j ≤ m)。
小明想知道是否能够选择一条树上的边砍断，使得对于每个 (ai , bi) 满足 ai和 bi 不连通，如果可以则输出应该断掉的边的编号（编号按输入顺序从 1 开始），否则输出 -1.
输入格式：
输入共 n + m 行，第一行为两个正整数 n，m。
后面 n − 1 行，每行两个正整数 xi，yi 表示第 i 条边的两个端点。
后面 m 行，每行两个正整数 ai，bi。
#include <iostream>
#include<bits/stdc++.h>
#define int long long using namespace std;
typedef pair<int ,int>pii;
const int N=1e5+10;vector<int>edge[N];//存储图（存邻接表）int m,n;
int w[N];//每一个边的边权map<pii,int>id;//存储边的编号bool dfs(int s,int u,int father,int v )
{if(u==v){return true;}for(int i=0;i<edge[u].size();i++){int son=edge[u][i];if(son==father)continue;if(dfs(s,son,u,v)){int ID=id[{u,son}];w[ID]++;return true;}}return false;}
void solve()
{cin>>n>>m;for(int i=0;i<n-1;i++){int x,y;cin>>x>>y;edge[x].push_back(y);edge[y].push_back(x);id[{x,y}]=id[{y,x}]=i;}for(int i=0;i<m;i++){int x,y;cin>>x>>y;dfs(x,x,-1,y);}int ans=-1;for(int i=n-1;i>=0;i--){if(w[i]==m){ans=i+1;//题目是从1开始编号break;}}cout<<ans<<endl;}
signed main()
{// 请在此输入您的代码ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;//cin>>twhile(t--)solve();return 0;
}
这篇关于蓝桥杯刷题-06-砍树-图遍历DFS⭐⭐⭐⭐的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
