CF982C Cut 'em all! DFS 树 * 二十一
1 second
256 megabytes
standard input
standard output
You're given a tree with nn vertices.
Your task is to determine the maximum possible number of edges that can be removed in such a way that all the remaining connected components will have even size.
The first line contains an integer nn (1≤n≤1051≤n≤105) denoting the size of the tree.
The next n−1n−1 lines contain two integers uu, vv (1≤u,v≤n1≤u,v≤n) each, describing the vertices connected by the ii-th edge.
It's guaranteed that the given edges form a tree.
Output a single integer kk — the maximum number of edges that can be removed to leave all connected components with even size, or −1−1 if it is impossible to remove edges in order to satisfy this property.
4
2 4
4 1
3 1
1
3
1 2
1 3
-1
10
7 1
8 4
8 10
4 7
6 5
9 3
3 5
2 10
2 5
4
2
1 2
0
In the first example you can remove the edge between vertices 11 and 44. The graph after that will have two connected components with two vertices in each.
In the second example you can't remove edges in such a way that all components have even number of vertices, so the answer is −1−1.
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define debug(a) cout << #a << " " << a << endl
using namespace std;
const int maxn = 1e5 + ;
const int mod = 1e9 + ;
typedef long long ll;
int hd[maxn], ne[maxn*], to[maxn*], num, n, siz[maxn], ans;
void add( int x, int y ) {
to[++num]=y, ne[num]=hd[x], hd[x]=num;
} void dfs( int x, int fa ) {
siz[x]=;
for( int i = hd[x]; i; i = ne[i] ) {
if(to[i]!=fa){
dfs(to[i],x);
siz[x]+=siz[to[i]];
}
}
if(!(siz[x]&))
siz[x]=,ans++;
} int main(){
std::ios::sync_with_stdio(false);
scanf("%d",&n);
int uu, vv;
for( int i = ; i < n; i ++ ) {
scanf("%d%d",&uu,&vv);
add(uu,vv), add(vv,uu);
}
if( n & ) {
puts("-1");
return ;
} dfs( , - ), ans--; printf("%d\n", ans );
return ;
}
最新文章
- Docker之Compose服务编排
- java抽象语法
- 在centos上配置IP
- maven 启动 报错 Fatal error compiling: 无效的目标发行版
- poj3159 Candies(差分约束,dij+heap)
- css hack一览
- 1934: [Shoi2007]Vote 善意的投票 - BZOJ
- 函数os_file_pread
- 腾讯.NET面试题
- sqoop1.9.7安装和使用
- NOIP2018普及初赛解析
- 5.基于优化的攻击——CW
- Dart 学习资料
- 表达式括号匹配(stack.cpp)
- Lucene增删改查
- Windows 2008禁止IE增强安全配置修改安全设置方法
- MYSQL中可以实现类似IF判断的方法
- ES6学习之let声明变量的学习
- 第十篇----------javascript函数的三种定义方式及区别
- Emgu学习之(三)——操作图像数据