【Codeforces Round #435 (Div. 2) B】Mahmoud and Ehab and the bipartiteness
The and Codeforces div round
2023-09-14 09:03:49 时间
【链接】h在这里写链接
【题意】
让你在一棵树上,加入尽可能多的边。
使得这棵树依然是一张二分图。
【题解】
让每个节点的度数,都变成二分图的对方集合中的点的个数就好。
【错的次数】
0
【反思】
在这了写反思
【代码】
#include <bits/stdc++.h> using namespace std; const int N = 1e5; vector <int> G[N + 10]; int n,color[N+10],cnt[2]; void dfs(int x, int tmp) { color[x] = tmp; cnt[tmp]++; for (int y : G[x]) { if (color[y] == -1) dfs(y, 1 - tmp); } } int main() { //freopen("F:\\rush.txt", "r", stdin); ios::sync_with_stdio(0), cin.tie(0); cin >> n; for (int i = 1; i <= n - 1; i++) { int x, y; cin >> x >> y; G[x].push_back(y); G[y].push_back(x); } memset(color, 255, sizeof color); dfs(1, 0); long long ans = 0; for (int i = 1;i <= n;i++) if (color[i] == 1) { ans += cnt[0] - (int)G[i].size(); } cout << ans << endl; return 0; }
相关文章
- 【已解决】在使用RocketMQ消费消息的时候,提示不支持SQL92的错误:CODE: 1 DESC: The broker does not support consumer to filter
- 【已解决】spring boot项目从mysql中获取数据候错误The driver has not received any packets from the server
- ORA-01378: The logical block size (string) of file string is not compatible with the disk sector size (media sector size is string and host sector size is string) ORACLE 报错 故障修复 远程处理
- ORA-32019: The parameter SPFILE cannot be updated in the server parameter file. ORACLE 报错 故障修复 远程处理
- ORA-39799: The column index number is out of range (max: number). ORACLE 报错 故障修复 远程处理
- ORA-48929: The trace record size exceeded the max size that can be read [string] ORACLE 报错 故障修复 远程处理
- ORA-08119: The new initrans will make the index too big ORACLE 报错 故障修复 远程处理
- ORA-13624: The task string is executing and cannot be deleted or modified. ORACLE 报错 故障修复 远程处理
- ORA-13631: The most recent execution of task string contains no results. ORACLE 报错 故障修复 远程处理
- ORA-13906: The tablespace is not of the right type. ORACLE 报错 故障修复 远程处理
- ORA-15464: STRIPE_COLUMNS of string is greater than the maximum of string ORACLE 报错 故障修复 远程处理
- Fiddler(三)Fiddler 报错creation of the root certificate was not successful详解程序员
- The valid characters are defined in RFC 7230 and RFC 3986详解编程语言
- MyD MySQL: The Innovative Database Management System for Improved Performance and Security(mydmysql)
- Unlock the Full Potential of Your System with Etc and Linux(Etclinux)
- Power Up Your Projects with Linux PP: Exploring the Best Tools and Techniques(linuxpp)
- Exploring the Benefits and Limitations of Oracle Chain Technology(oraclechain)
- Exploring the Power and Versatility of Linux External Libraries(linux外部库)
- Exploring the World of Linux with Ease: A Guide to Using Aoyou(遨游forlinux)
- Maximizing Database Efficiency: The Ultimate Guide to Implementing MSSQL Sharding and Partitioning(mssql分表分库)
- Exploring the Importance of Character Encoding and Primary Keys in MySQL(mysql字符主键)
- Exploring the Benefits and Uses of PPPD in the Linux Environment(pppdlinux)
- Exploring the Features and Benefits of MySQL 5.5(mysql5.5)
- Mastering Diff: The Essential Linux Tool for File Comparison and Version Control(difflinux工具)
- Exploring the Benefits of PAE in the Linux Kernel: Boosting Performance and Efficiency(linux内核pae)
- Exploring the Power of Redis Value: How It Can Improve Your Data Storage and Retrieval(redisvalue)
- MySQL中如何正确使用AND运算符(mysql中and怎么用)