欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

191214 二分图 咕

程序员文章站 2022-03-25 14:56:37
...

zgs说我们基础太差了T_T

二分图
(学这个的时候我终于感到了lyj聚聚说的要看证明才学的懂是多么的重要)
191214 二分图 咕
性质:
如果某个图为二分图,那么它至少有两个顶点,且其所有回路的长度均为偶数,任何无回路的的图均是二分图。

二分图判定:
染色法(实际上就是利用定义证明,把顶点放在不同的集合中),DFS实现
如果存在两条边顶点在同一个集合,那么不是二分图

代码:
(邻接矩阵太少用,咕)
向量函数实现(这个实际上hin慢)(这个代码要求整个图连通)

#include<bits/stdc++.h>
using namespace std;
#define in Read()
#define re register
int n,m;
int colour[205];
vector<int>node[205];

inline int in{
	int i=0,f=1;char ch;
	while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
	if(ch=='-')ch=getchar(),f=-1;
	while(ch>='0'&&ch<='9')i=(i<<1)+(i<<3)+ch-48,ch=getchar();
	return i*f;
}

inline bool Dfs(int v,int c){
	colour[v]=c;
	for(re int i=0;i<node[v].size();i++){
		if(colour[node[v][i]]==c)return false;
		if(!colour[node[v][i]]&&!Dfs(node[v][i],-c))return false;
	}
	return true;
}

int main(){
	n=in,m=in;
	for(re int i=1;i<=m;i++){
		int u=in,v=in;
		node[u].push_back(v);
		node[v].push_back(u);
	}
	
	Dfs(0,1)?printf("Yes\n"):printf("No\n");
	
	return 0;
}

数组实现邻接表实现

#include<bits/stdc++.h>
using namespace std;
#define in Read()
#define re register
const int NNN=205;
int n,m;
int tot,first[NNN],next[NNN<<1],aim[NNN<<1];
int colour[NNN];

inline int in{
	int i=0,f=1;char ch;
	while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
	if(ch=='-')f=-1,ch=getchar();
	while(ch<='9'&&ch>='0')i=(i<<1)+(i<<3)+ch-48,ch=getchar();
	return i*f;
}

inline void Add(int u,int v){
	tot++;
	next[tot]=first[u];
	first[u]=tot;
	aim[tot]=v;
}

inline bool Dfs(int u,int c){
	colour[u]=c;
	for(re int e=first[u];e;e=next[e]){
		int v=aim[e];
		if(colour[v]==c)return false;
		if(!colour[v]&&!Dfs(v,-c))return false;
	}
	return true;
}

int main(){
	n=in,m=in;
	for(re int i=1;i<=m;i++){
		int u=in+1,v=in+1;
		Add(u,v);
		Add(v,u);
	}
	for(re int i=1;i<=n;i++){
		if(!colour[i])break;
		if(Dfs(i,1))printf("No\n");
		return 0;
	}
	printf("Yes\n");
	return 0;
}

练习
做着做着就变成了并查集(一不小心翻到题解看到这个方法是可以实现的)

相关标签: 图论