网站建设证有,哪个女装网站做的好,成都小程序开发方案,网站托管是什么正题
题目链接:https://codeforces.com/gym/103049/problem/J 题目大意 nnn个点mmm条边的一张无向图#xff0c;选出一条路径后去掉路径上的点#xff0c;然后将剩下的点分成点数相等的两份使得两份之间没有边连接。 1≤n,m≤21051\leq n,m\leq 2\times 10^51≤n,m≤2105 解…正题
题目链接:https://codeforces.com/gym/103049/problem/J 题目大意
nnn个点mmm条边的一张无向图选出一条路径后去掉路径上的点然后将剩下的点分成点数相等的两份使得两份之间没有边连接。
1≤n,m≤2×1051\leq n,m\leq 2\times 10^51≤n,m≤2×105 解题思路
先跑出dfsdfsdfs树这样就保证了所有的非树边都是返祖边。
发现如果我们选出树上一条根节点出发的路径那么其他子树之间一定是不连通的因为要么子树之间有环要么往上的环被删除。
所以问题就变成了选出一条从根出发的路径然后把其他的分成大小相等的两份。
考虑贪心解决我们走到一个点时可以把儿子的子树大小从小到大排列然后两边那边不够就加给哪边加剩最大的一个再继续往下分。
因为这样分的差一定不大于最大的那个所以肯定是对的。 code
#includecstdio
#includecstring
#includealgorithm
#includevector
using namespace std;
const int N2e510;
int n,m,siz[N],mark[N];
vectorint G[N],T[N],p;
void dfs(int x,int fa){siz[x]1;for(int i0;iG[x].size();i){int yG[x][i];if(yfa||siz[y])continue;T[x].push_back(y);dfs(y,x);siz[x]siz[y];}return;
}
bool cmp(int x,int y)
{return siz[x]siz[y];}
void calc(int x,int fa,int a,int b){sort(T[x].begin(),T[x].end(),cmp);p.push_back(x);int lr0;for(int i0;iT[x].size();i){int yT[x][i];if(yfa)continue;if(!lr)lry;else if(ab)asiz[y],mark[y]1;else bsiz[y],mark[y]2;}if(abasiz[lr]b){mark[lr]1;return;}if(abbsiz[lr]a){mark[lr]2;return;}calc(lr,x,a,b);return;
}
void print(int x,int fa,int z){if(!mark[x])mark[x]mark[fa];for(int i0;iT[x].size();i)if(T[x][i]!fa)print(T[x][i],x,z);if(mark[x]z)printf(%d ,x);return;
}
int main()
{scanf(%d%d,n,m);for(int i1;im;i){int x,y;scanf(%d%d,x,y);G[x].push_back(y);G[y].push_back(x);}dfs(1,0);calc(1,1,0,0);int w(n-p.size())/2;printf(%d %d\n,p.size(),w);for(int i0;ip.size();i)printf(%d ,p[i]);mark[0]0;putchar(\n);print(1,0,1);putchar(\n);print(1,0,2);return 0;
}
