二分图 |
您所在的位置：网站首页 › 12个顶点的二分图 › 二分图 |
二分图
|
二分图
二分图，又叫二部图，将所有点分成两个集合，使得所有边只出现在集合之间的点之间，而集合内部的点之间没有边。 当一个图只有n个顶点，没有边时，只能分成一个集合，也是二分图 二分图，当且仅当图中没有奇数环。 所以，只要图中没有环 或者 只有偶数环，一定是二分图。 从而推出，树一定是二分图。 二分图不一定是连通图，也可能是非连通图。 染色法定义一个数组，int color[N]，给每个顶点规定三种状态其中一个，0代表还未开始染色，1代表染成一种颜色，2代表染成另一种颜色，由此将所有顶点分成两个集合：1和2。 1. 从哪个起点开始染色呢？ 如果是连通图的话，从任何一个顶点染色都可以，因为通过任何一个起点都可以遍历到所有顶点； 若是非连通图，最少要取出每个连通子图的其中一个顶点才行。 为了方便起见，每个点都作为起点，当以该点为起点开始染色时，先判断这个点是否已经染过色了，如果没有染色，再开始进行染色。 这样的话，顶多是多循环几次，有效的循环染色次数还是取决于连通图的个数； 当N个点的整个图都是连通的话，只会染色一次，剩下N-1次都是无效循环罢了。 2. 起点处染什么颜色 起点处随意染色。 非联通图之间不同染色的集合可以排列组合，因此起点处选择哪种染色都行。 3. 怎么染色？ 假设起点染色为颜色1，那么它的下一层所有结点就染色为颜色2，然后再往下一层就是颜色1……依次类推。 不存在环的话就此结束； 若是存在环(i,k1,k2,……,kn,i)： 奇数环，起点 i 染色为颜色1，最后一个位置 kn 染色也为颜色1，那么它的下一个位置，就是起点要染色成颜色2，矛盾，染色失败，不是二分图。偶数环，起点 i 染色为颜色1，最后一个位置 kn 染色也为颜色2，那么它的下一个位置，就是起点要染色成染色1，不矛盾，该环染色结束。重边和自环的问题，可以通过判断要染色的结点是否被染过色而自动被过滤掉。 因此，重边和自环可以存储图中，无影响。 时间复杂度O(m+n) BFS染色
因此，队列中的每个元素要记录两个信息，1. 结点编号；2. 染成的颜色。 1代表一种颜色集合，2代表一种颜色集合， 当第i层是颜色1时，i+1层就是颜色2（3-1）；当第i层是颜色2时，i+1层就是颜色1（3-2），所以可以统一操作： 即，当第i层是颜色x时，i+1层就是颜色3-x #include #include using namespace std; #define ff first #define ss second typedef pair PII; //first表示节点编号，second表示该结点染成的颜色 const int N=1e5+10,M=2e5+10; "无向图，边要存储双倍" PII q[N]; "图中的点不会重复加入队列，所以tt最多到N" int hh,tt=-1; int h[N],e[M],ne[M],idx; //无向无权图 int clr[N]; //记录每个点的染色，0代表未染色，1 2分别代表两种不同的颜色,clr数组兼顾了vis数组的作用，全局变量，默认为0 int n,m; void add(int a,int b)//a->b { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } bool bfs(int vv,int cc) { //先初始化，起点vv染色为cc clr[vv]=cc; q[++tt]={vv,cc}; while (hh "~i等价于i!=-1，-1的二进制补码全1，只有-1取反是全0，此时停止，其他情况下~i都不是0" int j=e[i]; "v->j的边 不同于!i，所有的非零数!i都是0 " if (!clr[j]) clr[j]=3-c,q[++tt]={j,clr[j]}; //没有染色的情况 else if (clr[j]==c) return false; //存在奇数环，矛盾，染色失败 //还有一种情况，已经染色且clr[j]==3-c，说明存在偶数环，不用染色了，可以跳过，处理其它相邻的点。 } //从顶点v出发有很多出边，除了构成回路外，还有其它的点j } return true; "因队列为空而退出，说明一个连通图中全部染色完成。" "因为我们不知道一个连通图中有多少个顶点，所以必须等队列为空退出才行，中途退出则说明染色失败" } int main() { memset(h,-1,sizeof h); scanf("%d%d",&n,&m); int a,b; while (m--) { scanf("%d%d",&a,&b); add(a,b),add(b,a); } //判断是否是二分图 bool tag; for (int i=1;i//每一次bfs就是给一个连通图染色，每一个连通图都从1号颜色开始染色 tag=bfs(i,1); //染色，并返回是否染色成功;起点i染色为颜色1 if (tag==false) break; //染色失败就退出 } } tag==true?puts("Yes"):puts("No"); return 0; } DFS染色 #include #include using namespace std; const int N=1e5+10,M=2e5+10; int h[N],e[M],ne[M],idx; int clr[N]; int n,m; void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } bool dfs(int v,int c)//欲将结点为v的顶点染色为c { "从上到下染色，然后回溯返回是否染色成功" if (clr[v]==c) return true; //偶数环，该路径染色结束，成功 else if (clr[v]==3-c) return false; //奇数环，该路径染色结束，失败 else { //该点没染色的情况 clr[v]=c; for (int i=h[v];~i;i=ne[i]) { //给下一层的每个点都进行染色 if (dfs(e[i],3-c)==false) return false; //如果中途发现染色失败就返回 } "调用函数的同时使用返回值" return true; //染色成功 } } int main() { memset(h,-1,sizeof h); scanf("%d%d",&n,&m); int a,b; while (m--) { scanf("%d%d",&a,&b); add(a,b),add(b,a); } bool tag; for (int i=1;i tag=dfs(i,1); if (tag==false) break; } } tag==true?puts("Yes"):puts("No"); return 0; }dfs可以有很多写法，上面每次递归进入时都要判断一下染色的点是否合理； 也可以认为每次进入递归时要染色的点都是合理染色的点。 bool dfs(int u,int c) { clr[u]=c; for (int i = h[u]; i != -1; i = ne[i]) { int j=e[i]; if (!clr[j]) { //1 2分别代表两种染色，u染了1，它下一个j就染2；染了2，j就染1 if (dfs(j, 3 - c) == false) return false; //综上，u染c，j染3-c } else if (clr[j]==c) return false; //这也是最后一次递归结束的条件 } //当前要染色3-c，但是如果已经染色c的话，说明存在奇数环，不是二分图 return true; } |
【本文地址】
今日新闻 |
推荐新闻 |