《网站推广策划》,好的设计师网站有哪些,免费wordpress外贸企业主题,可信网站是什么给定一个 n 个点 n 条边的无向图#xff0c;你需要求有多少种选择图上的一个点 p 和一条边 (x,y) 的方案#xff0c;使得删去 (x,y) 后图变成一棵树#xff0c;且这棵树以 p 为根时每个节点的儿子个数均不超过 3。保证至少存在一种这样的方案。
Input 输入的第一行一个整数…给定一个 n 个点 n 条边的无向图你需要求有多少种选择图上的一个点 p 和一条边 (x,y) 的方案使得删去 (x,y) 后图变成一棵树且这棵树以 p 为根时每个节点的儿子个数均不超过 3。保证至少存在一种这样的方案。
Input 输入的第一行一个整数 n2≤n≤105 表示节点数接下来 n 行每行两个整数 x,y1≤x,y≤n 描述图上的一条边。保证图中没有重边自环。
Output 输出一行一个正整数表示答案。
Input 6 1 2 1 3 1 4 1 5 1 6 2 3
Output 10
解析
n个点n条边所以该图就成一个环。只有将环中的一条边删去该图才能变为一棵树。
#include bits/stdc.h
using namespace std;
#define int long long
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef pairint,int PII;
const int N2e610;
vector int g[N];
map int,int k;
int p[N];
int d[N];
bool vis[N];
vector PII q; //储存成环的边
int n;
void dfs(int u,int pa)
{p[u]pa;vis[u]1;for (auto v:g[u]){if (vpa) continue;if (vis[v]1q.size()0) //当点 v 被再次遍历时现在已经建成一个环了就可以回溯将环中的每条边放入队列 q 中{q.push_back({u,v});while (p[u]!v){q.push_back({u,p[u]});up[u];}q.push_back({u,p[u]});}if (vis[v]1) continue; //走过的点不用继续操作了否则会死循环dfs(v,u);}
}
signed main()
{ios;cinn;for (int i1;in;i){int u,v;cinuv;g[u].push_back(v);g[v].push_back(u);d[u];d[v];}for (int i1;in;i){k[d[i]]; //记录度数相同的点的数量}//for (auto x:k) coutx.first x.secondendl;dfs(1,0);//for (auto x:q) coutx.first x.secondendl;int ans0;for (auto x:q) //遍历每条要删掉的边{int dud[x.first];int dvd[x.second];k[du]--;k[dv]--;k[du-1];k[dv-1];int res0;bool flag0;for (auto y:k) //删除边后再遍历每个点判断能否成为根节点{int cnty.first;int sy.second;if (cnt3) res s;if (cnt5s0) flag1; //既当不了根节点也当不了儿子节点}if (flag0) ans res;k[du]; //还原k[dv];k[du-1]--;k[dv-1]--;}coutans;return 0;
}
