朋友做的网站图片不显示/网络运营培训哪里有学校

二分图概念： 设 G=(V,E) 是一个无向图，如果顶点集合 V 可分割为两个互不相交的子集 (A,B)，并且每条边 (i,j)∈E 的两个端点 i 和 j 分别属于这两个不同的顶点子集，则称图 G 为一个二分图。
二分图判定： 如果图中不存在奇数环，则这个图是二分图

1. 二分图染色法

输入：
4 4
1 3
1 4
2 3
2 4
输出：
Yes

#include<iostream>//染色法即将相邻的两个点赋成不同的值，若在赋值的过程中出现相邻的两个顶点值相同，则不是二分图
#include<vector>
using namespace std;int n,m;
vector<int> v[100010];
int color[100010];bool dfs(int u,int c)
{color[u]=c;for(int i=0;i<v[u].size();i++){int j=v[u][i];if(!color[j]){if(!dfs(j,3-c)) return false;//上一层的错误}else if(color[j]==c) return false;//当前一层的错误}return true;
}int main()
{cin>>n>>m;int a,b;while(m--){scanf("%d %d",&a,&b);v[a].push_back(b);v[b].push_back(a);}bool flag=true;for(int i=1;i<=n;i++){if(!color[i]){if(!dfs(i,1)){flag=false;break;}}}if(flag) cout<<"Yes"<<endl;else cout<<"No"<<endl;return 0;
}

2. 树与二分图

输入：
7
1 2
2 3
2 4
2 5
2 6
4 7
输出：
4

#include<iostream>
#include<vector>
#include<stdio.h>
using namespace std;int n;
long long ji,ou;//根据二分图的判定性质，只有树的奇数层上的点和偶层上的点链接才能构成偶数环，而构成偶数环，才能保证是二分图
vector<int> v[1000010];
bool st[1000010];void dfs(int u,int dep)
{st[u]=true;if(dep%2==1) ji++;else ou++;for(int i=0;i<v[u].size();i++){if(!st[v[u][i]]) dfs(v[u][i],dep+1);}
}int main()
{cin>>n;int a,b;for(int i=0;i<n-1;i++){scanf("%d %d",&a,&b);v[a].push_back(b);v[b].push_back(a);}dfs(1,1);//第一个值传的是节点的编号，理论上讲，这里传任何一个合法的节点都可以，因为1在任何时候都合法，因此方便起见，这里传1cout<<ji*ou-(n-1)<<endl;//减去树中已存在的n-1条边，这些边恰好都在乘机里，因为他们互为奇层偶层的关系return 0;
}

3. 二分图的最大匹配(顶点之间的两两配对)

输入：
2 2 4
1 1
1 2
2 1
2 2
输出
2

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;int n1,n2,m;
int res;
vector<int> v[510];
bool st[510];//右边是否被访问过
int match[510];//下标为右边，值为左边bool find(int x)
{for(int i=0;i<v[x].size();i++){int j=v[x][i];if(!st[j])//在回溯的过程中，这里挡住了已经找过的门槛{st[j]=true;if(match[j]==0||find(match[j]))//左边条件好理解，j没有被匹配过，直接匹配成功；右边条件是被匹配过的情况，这时候需要回溯，看左边这个要匹配的还有没有其他的人选，一层一层的往上寻求答案{match[j]=x;return true;}}}return false;
}int main()
{cin>>n1>>n2>>m;while(m--){int a,b;scanf("%d %d",&a,&b);v[a].push_back(b);//这里只需要左边指向右边即可}for(int i=1;i<=n1;i++){memset(st,false,sizeof st);if(find(i)) res++;}cout<<res<<endl;return 0;
}