二分图练习

在这里插入图片描述
对于二分图我们可以用染色法

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N = 2e6+5;
int e[N],ne[N],h[N],idx = 0;
int colo[N];
int num = 0;

void add(int x,int y){
	e[++idx] = y;
	ne[idx] = h[x];
	h[x] = idx;
}
void dfs(int nod,int c){
	colo[nod] = c;
	if(c==1) num++;
	for(int i = h[nod];i!=-1;i = ne[i]){
		int to = e[i];
		if(!colo[to]){
			dfs(to,3-c);
			//cout << nod << endl;
		}
		//cout << nod<< " sb " << endl;
	}
}
signed main(){
	int n;
	cin >> n;
	memset(h,-1,sizeof h);
	for(int i=1;i<=n-1;i++){
		int a,b;
		cin >> a >> b;
		add(a,b),add(b,a);
		
	}
	dfs(1,1);
	cout << (n-num)*num-(n-1);
	return 0;
}

相关推荐

  1. <span style='color:red;'>二分</span><span style='color:red;'>图</span>

    二分

    2024-07-10 23:54:02      26 阅读
  2. 数组练习(2)二分查找

    2024-07-10 23:54:02       32 阅读
  3. 二分板子

    2024-07-10 23:54:02       35 阅读

最近更新

  1. 2742. 给墙壁刷油漆

    2024-07-10 23:54:02       0 阅读
  2. longjmp和多线程:读写线程实例

    2024-07-10 23:54:02       0 阅读
  3. 【CF】1216F-WiFi 题解

    2024-07-10 23:54:02       0 阅读
  4. 牛客周赛 Round 52VP(附D的详细证明)

    2024-07-10 23:54:02       0 阅读
  5. Android13 应用代码中修改热点默认密码

    2024-07-10 23:54:02       0 阅读
  6. 【React】事件绑定、React组件、useState、基础样式

    2024-07-10 23:54:02       0 阅读
  7. postman接口测试工具详解

    2024-07-10 23:54:02       0 阅读
  8. Symfony数据库抽象层:深入理解其工作原理

    2024-07-10 23:54:02       0 阅读
  9. 设计模式--职责链模式

    2024-07-10 23:54:02       0 阅读

热门阅读

  1. yolov5中训练长条型目标召回率低问题

    2024-07-10 23:54:02       8 阅读
  2. openssl error:0A000126:SSL routines:ssl3_read_n:unexpected eof

    2024-07-10 23:54:02       9 阅读
  3. 各种软件启动方式

    2024-07-10 23:54:02       6 阅读
  4. 【创作纪念日】我的三周年创作纪念日

    2024-07-10 23:54:02       7 阅读
  5. Github 2024-07-07 开源项目日报 Top10

    2024-07-10 23:54:02       8 阅读
  6. 部署LVS-DR群集

    2024-07-10 23:54:02       5 阅读
  7. python的列表推导式

    2024-07-10 23:54:02       8 阅读