精华内容
下载资源
问答
  • 怎么判定一个图是否为二分图 ? 从其中一个定点开始,将跟它邻接的点染成与其不同的颜色,最后如果邻接的点有相同颜色,则说明不是二分图,每次用bfs遍历即可。
  • 染色法判断二分图

    2020-08-11 08:51:28
    染色法来染色节点, 如果途中没有出现矛盾的点,那么说明该无向图是二分图。 伪代码如下 for(int i = 1; i <= n; i++) if(i未被遍历过) dfs(i); 题目 代码 #include<cstring> #include<...

    用染色法来染色节点, 如果途中没有出现矛盾的点,那么说明该无向图是二分图。
    伪代码如下

    for(int i = 1; i <= n; i++)
    	if(i未被遍历过)
    		dfs(i);
    

    题目
    在这里插入图片描述
    代码

    #include<cstring>
    #include<algorithm>
    #include<iostream>
    
    using namespace std;
    
    const int N = 100010, M = 200010;
    int n, m;
    int e[M], ne[M], idx, h[N];
    int color[N];
    
    void add(int a, int b){
        e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
    }
    
    bool dfs(int u, int c){//节点u, 颜色为c
        color[u] = c;
        
        for(int i = h[u]; i != -1; i = ne[i]){
            int j = e[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;
        
        memset(h, -1, sizeof h);
        
        while(m -- ){
            int a, b;
            cin >> a >>b;
            add(a, b), add(b, a);
        }
        
        //二分染色法
        bool flag = true;
        for(int i = 1; i <= n; i++){
            if(!color[i])
                if(!dfs(i, 2)){ 
                    flag = false;
                    break;
                }
        }
        if(flag) puts("Yes");
        else puts("No");
        return 0;
    }
    
    展开全文
  • 请你判断这个图是否是二分图。 输入格式 第一行包含两个整数n和m。 接下来m行,每行包含两个整数u和v,表示点u和点v之间存在一条边。 输出格式 如果给定图是二分图,则输出“Yes”,否则输出“No”。 数据范围...

    题目:

    给定一个n个点m条边的无向图,图中可能存在重边和自环。

    请你判断这个图是否是二分图。

    输入格式

    第一行包含两个整数n和m。

    接下来m行,每行包含两个整数u和v,表示点u和点v之间存在一条边。

    输出格式

    如果给定图是二分图,则输出“Yes”,否则输出“No”。

    数据范围

    1≤n,m≤10^5

    输入样例:

    4 4
    1 3
    1 4
    2 3
    2 4
    

    输出样例:

    Yes

    代码:

    n, m = map(int, input().split())
    st = [0]*(n+1) # 染色数组
    idx = 0
    e, ne = [0]*(2*m+1), [0]*(2*m+1)
    h = [-1]*(n+1)
    
    
    def add(a, b):
        global idx
        e[idx], h[a], ne[idx] = b, idx, h[a]
        idx += 1
    
    def bfs(i, c):
        queue = [(i, c)]
        hh, tt = 0, 0
        st[i] = c
        while hh <= tt:
            t, c = queue[hh]
            hh += 1
            i = h[t]
            while i != -1:
                j = e[i]
                if st[j] == 0:
                    st[j] = 3-c
                    queue.append((j, 3-c))
                    tt += 1
                elif st[j] == c:
                    return False
                i = ne[i]
        return True      
    
    for _ in range(m):
        a, b = map(int, input().split())
        add(a, b)
        add(b, a)
    
    flag = True
    for i in range(1, n+1):
        if st[i] == 0 and not bfs(i, 1):
            flag = False; break
    if flag: print('Yes')
    else: print('No')
        

     

    展开全文
  • 染色法判断二分图

    2019-10-01 19:51:10
    二分图的定义 图G=(V,E),顶点集V可分割为两个互不相交的子集,并且图中每条边依附的两个顶点都分属于这两个互不相交的子集,两个子集内的顶点不相邻。-----百科 就是当一个东西可以分成两半的时候,你可以问自己...

    写的很菜 , 欢迎建议、补充

    二分图的定义

    图G=(V,E),顶点集V可分割为两个互不相交的子集,并且图中每条边依附的两个顶点都分属于这两个互不相交的子集,两个子集内的顶点不相邻。-----百科

    就是当一个东西可以分成两半的时候,你可以问自己一下这满足不满足二分图的性质。

    解释的很草率 ↑    ,   题解里向来都是说 : "显而易见这是二分图", 我也不好这么说 , 题做得还少, 这几天多练练没准就找到手感了 。

    当你定好了解题的方向,那么如何判定这个是二分图呢 。

    染色法 。

    需要两种颜色,我们从任意点开始染色, 把与其相邻的点染成与它相反的颜色 , 整个图染完色之后,如果满足相连的两个点颜色都不同, 那么就可以断定它是二分图了 , 如果发现相连点颜色相同 ,那就满足不了二分图的定义了。  

    这个染色过程通过BFS或者DFS实现。

    下面贴个BFS代码  , DFS同理。

     1 void connect(int x,int y)//拿邻接表存的图,用vector也可以。 
     2 {
     3     pre[++cnt]=last[x];
     4     other[cnt]=y;
     5     last[x]=cnt;
     6 } 
     7 void BFS(int x)
     8 {
     9     queue <int>q;
    10     q.push(x);
    11     color[x]=1;            //BFS染色 
    12     while(!q.empty())
    13     {
    14         int tmp=q.front();
    15         q.pop();
    16         for(int i=last[tmp];i;i=pre[i])
    17         {
    18             int to=other[i];
    19             if(to==tmp)continue;
    20             if(color[to]==color[tmp]){        //发现相邻点的颜色相等,于是这个图不是二分图 
    21                 exit(0);
    22             }
    23             else{
    24                 color[to]=1^color[tmp];        //把相邻点涂成相反的颜色,然后把这个点加入队列 
    25                 q.push(to);
    26             }
    27         }
    28     }
    29 }
    30 int main()
    31 {
    32     memset(color,-1,sizeof(color));
    33     for(int i=1;i<=N;i++)
    34         if(color[i]==-1)BFS(i);                //=、= 
    35 }

    判断二分图的代码就这样↑

     

    下面给道可爱的例题

    NOIP2008  双栈排序 (可以在LuoguP1155提交)

    戳链接https://www.luogu.org/problem/show?pid=1155看题面,就不粘贴了

    这个题就是有一个序列,给你两个栈,通过进栈退栈输出一个排序的序列 

    (按理来说肯定不能纯模拟做,虽然题解里有一个超级长的纯模拟代码)

    联想到二分图,我们应该去思考如何把这些数分成两部分,分别放进两个栈里

    下面我们要考虑怎样的两个元素可以放到一个栈里面,

    显然的 ,当i<j<k , a[k]<a[i]<a[j],i和j是不能放到同一个栈里的 ,于是i,j就可以构成图的两个子集的一条边 

    我们枚举出来所有的i,j 进行连边,

        for(int i=N-1;i>=1;i--)sufmin[i]=min(sufmin[i+1],a[i+1]);
        for(int i=1;i<=N;i++)
            for(int j=i+1;j<=N;j++)
                if(a[i]<a[j]&&a[i]>sufmin[j]){
                connect(i,j);connect(j,i);
            }

     

    之后利用上面的染色法判定二分图,就可以把所有的数分成两部分,再进行简单的模拟,就可以得到答案了。

    如果不是这个不是二分图,那就说明无解。

     

    先写这么多了,很啰嗦求见谅,学了新的再加内容。

     

    转载于:https://www.cnblogs.com/Elfish/p/7535169.html

    展开全文
  • 染色法判定二分图一、二分图二、染色法1.算法实现思路2.DFS深度优先遍历代码实现3.BFS广度优先遍历代码实现 一、二分图 一定不含有奇数环,可能包含长度为偶数的环, 不一定是连通图 二分图是图论中的一种特殊模型...

    一、二分图

    • 一定不含有奇数环,可能包含长度为偶数的环, 不一定是连通图

    二分图是图论中的一种特殊模型。设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B),则称图G为一个二分图。简单来说,如果图中点可以被分为两组,并且使得所有边都跨越组的边界,则这就是一个二分图。准确地说:把一个图的顶点划分为两个不相交子集 ,使得每一条边都分别连接两个集合中的顶点。如果存在这样的划分,则此图为一个二分图,如下图所示的全都是二分图:
    在这里插入图片描述
    关于二分图有一个重要的定理:G为二分图的充要条件是G中的每一个环的长度都是偶数 在这里就不证明了。

    二、染色法

    1.算法实现思路

    • 我们规定1或2代表一个点属于两个集合。
    • 首先我们任选一个点染色成1,把和它相连的所有点染色成2。
    • 然后再把所有和染色成2的点相邻的点染色成1
    • 在每一次染色点时首先要判断一下这个点是否被染色过,如果被染色过并且和上一个点颜色相同,则代表染色失败,该图不是二分图。

    2.DFS深度优先遍历代码实现

    代码思路:

    • 染色可以使用1和2区分不同颜色,用0表示未染色
    • 遍历所有点,每次将未染色的点进行dfs, 默认染成1或者2
    • 由于某个点染色成功不代表整个图就是二分图,因此只有某个点染色失败才能立刻break/return
      • 染色失败相当于存在相邻的2个点染了相同的颜色
    //#pragma GCC optimize(2)
    #include<iostream>
    #include<iomanip>
    #include<cstdio>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<queue>
    #include<vector>
    #include<map>
    #include<stack>
    #include<set>
    #include<bitset>
    #include<ctime>
    #include<cstring>
    #include<list>
    #define ll long long
    #define ull unsigned long long
    #define INF 0x3f3f3f3f
    #define mem(a,b) memset(a,b,sizeof(a))
    using namespace std;
    typedef  pair<int, int> PII;
    const int N = 1e5 + 7,M=2e5+7;
    
    int n, m;
    int h[M], e[M], ne[M];  //邻接表存图
    int id = 1;
    int color[N];  //每个点的颜色
    
    void add(int a, int b)  //加边函数
    {
    	e[id] = b, ne[id] = h[a], h[a]=id++;
    }
    
    bool dfs(int u, int x)   //把u染色成x
    {
    	color[u] = x;
    	for (int i = h[u]; i != -1; i = ne[i])   //遍历与u相连的所有点
    	{
    		int j = e[i];
    		if (!color[j])  //如果这个点没被染色过就染色
    		{
    			if (!dfs(j, 3 - x))return false;  //染色失败就返回false
    		}
    		if (color[j] == color[u])return false;  //之前被染色并且和父节点颜色一样就染色失败
    	}
    	return true;
    }
    
    void solve()
    {
    	mem(h, -1);
    	cin >> n >>  m;
    	for (int i = 0; i < m; i++)
    	{
    		int a, b;
    		cin >> a >> b;
    		add(a, b);
    		add(b, a);
    	}
    	for (int i = 1; i <= n; i++)
    	{
    		if (!color[i])
    		{
    			if (!dfs(i, 1))
    			{
    				cout << "No" << endl;
    				return;
    			}
    		}
    		
    	}
    	cout << "Yes" << endl;
    }
    
    int main()
    {
    	std::ios::sync_with_stdio(false);
    	cin.tie(0), cout.tie(0);
    	solve();
    	return 0;
    }
    
    

    3.BFS广度优先遍历代码实现

    代码思路

    • 颜色 1 和 2 表示不同颜色, 0 表示 未染色
    • 定义queue是存PII,表示 <点编号, 颜色>,
    • 同理,遍历所有点, 将未染色的点都进行bfs
    • 队列初始化将第i个点入队, 默认颜色可以是1或2
      • while (队列不空)
        • 每次获取队头t, 并遍历队头t的所有邻边
        • 若邻边的点未染色则染上与队头t相反的颜色,并添加到队列
        • 若邻边的点已经染色且与队头t的颜色相同, 则返回false
    //#pragma GCC optimize(2)
    #include<iostream>
    #include<iomanip>
    #include<cstdio>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<queue>
    #include<vector>
    #include<map>
    #include<stack>
    #include<set>
    #include<bitset>
    #include<ctime>
    #include<cstring>
    #include<list>
    #define ll long long
    #define ull unsigned long long
    #define INF 0x3f3f3f3f
    #define mem(a,b) memset(a,b,sizeof(a))
    using namespace std;
    typedef  pair<int, int> PII;
    const int N = 1e5 + 7,M=2e5+7;
    
    int n, m;
    int h[M], e[M], ne[M];
    int id = 1;
    int color[N];
    
    void add(int a, int b)
    {
    	e[id] = b, ne[id] = h[a], h[a]=id++;
    }
    
    bool bfs(int u) {
    	queue<PII> q;
    	q.push( { u, 1 });
    	color[u] = 1;
    
    	while (!q.empty()) {
    		auto t = q.front();
    		q.pop();
    		int ver = t.first, c = t.second;
    
    		for (int i = h[ver]; i != -1; i = ne[i]) {
    			int j = e[i];
    
    			if (!color[j])
    			{
    				color[j] = 3 - c;
    				q.push ( { j, 3 - c });
    			}
    			else if (color[j] == c) return false;
    		}
    	}
    
    	return true;
    }
    
    
    void solve()
    {
    	mem(h, -1);
    	cin >> n >>  m;
    	for (int i = 0; i < m; i++)
    	{
    		int a, b;
    		cin >> a >> b;
    		add(a, b);
    		add(b, a);
    	}
    	for (int i = 1; i <= n; i++)
    	{
    		if (!color[i])
    		{
    			if (!bfs(i))
    			{
    				cout << "No" << endl;
    				return;
    			}
    		}
    		
    	}
    	cout << "Yes" << endl;
    }
    
    int main()
    {
    	std::ios::sync_with_stdio(false);
    	cin.tie(0), cout.tie(0);
    	solve();
    	return 0;
    }
    
    

    作者:Avalon Demerzel,喜欢我的博客就点个赞吧,更多图论与数据结构知识点请见作者专栏《图论与数据结构》

    展开全文
  • 请你判断这个图是否是二分图。 输入格式 第一行包含两个整数n和m。 接下来m行,每行包含两个整数u和v,表示点u和点v之间存在一条边。 输出格式 如果给定图是二分图,则输出“Yes”,否则输出“No”。 数据范围 1≤n,...
  • 染色法判定二分图

    2021-05-02 21:51:12
    染色法判定二分图本题分析AC代码三、时间复杂度 前言 复习acwing算法基础课的内容,本篇为讲解基础算法:染色法判定二分图,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上。 一、二分图 二分图当且...
  • 先谈一下二分图相关: 一个图是二分图的充分必要条件: 该图对应无向图的所有回路必定是偶环(构成该环形的边的数量为...交叉染色法。 随机选择一个点,染成红色,把所有跟它相邻的点染成绿色,再由被染色的...
  • 染色法判定二分图 在学习染色判定二分图之前,要先了解二分图的一些性质; 1.二分图没有奇数环,所谓奇数环就是一个环的顶点数为奇数; 2.结合性质1,我们知道二分图染色必定是不会矛盾的,比如我们用两种颜色给二分...
  • 染色问题用什么去实现 : dfs 染色: 一旦给一个点染上颜色,其所在的连通部分中的所有点都要被染上颜色...注意: 题所给的不一定是连通。 class Solution { public: bool dfs(vector<vector<int>...
  • 染色法判断二分图 什么是二分图 二分图就是只你可以把一个图的点拉到左右两边。 这样它们就会变成两个集合。 那我们把原来图的边保留进这两个集合中。 最后如果我们可以使得这两个集合内部没有任何边,所有边都是...
  • 题目大意:给你一副无向联通图,判断是不是二分图 题目思路:交叉染色法  下面着重介绍下交叉染色法的定义与原理  首先任意取出一个顶点进行染色,和该节点相邻的点有三种情况:  1.未染色 那么继续染色此节点...
  • 请你判断这个图是否是二分图。 输入格式 第一行包含两个整数 n 和 m。 接下来 m 行,每行包含两个整数 u 和 v,表示点 u 和点 v 之间存在一条边。 输出格式 如果给定图是二分图,则输出 Yes,否则输出 No。 数据范围...
  • NYOJ1015 二部图(染色法判断二分图)

    千次阅读 2017-09-24 01:00:01
    二部图又叫二分图,我们不是求它的二分图最大匹配,也不是完美匹配,也不是多重匹配,而是证明一个图是不是二部图。证明二部图可以用着色来解决,即我们可以用两种颜色去涂一个图,使的任意相连的两个顶点颜色不...
  • 二分图 二分图是图论中的一种特殊模型,可理解为将一个图中...染色法判断二分图 题目链接–染色法判断二分图 #include<iostream> #include<cstring> #include<algorithm> using namespace std; const
  • acwing 860染色法判断二分图 **二分图定义: 顶点集V可分割为两个互不相交的子集,并且图中每条边依附的两个顶点都分属于这两个互不相交的子集,两个子集内的顶点不相邻。 二分图性质: 1.如果两个集合中的点分别染成...
  • 请你判断这个图是否是二分图。 输入格式 第一行包含两个整数n和m。 接下来m行,每行包含两个整数u和v,表示点u和点v之间存在一条边。 输出格式 如果给定图是二分图,则输出“Yes”,否则输出“No”。 数据范围 1≤ n...
  • 南阳理工1015 (染色法判断二分图

    千次阅读 2015-08-14 16:47:41
    二分图简介】 二分图:简单来说,如果图中点可以被分为两组,并且使得所有边都跨越组的边界,则这就是一个二分图。 准确地说:把一个图的顶点划分为两个不相交集 X 和 Y ,使得每一条边都分别连接X 、 Y 中的...
  • bfs染色法判定二分图

    2019-10-08 13:26:19
    #include<iostream> #include<queue> #include<cstring> #include<cstdio> using namespace std; int mapp[2005][2005],color[2005]; int n,m,k; int bfs(int x) ... col...
  • 时间复杂度m+n #include<iostream> #include<string.h> using namespace std; const int N=200010; int n,m; int h[N],ne[N],idx,e[N]; int color[N]; void add(int a,int b)... ne[idx]=h[a],e[idx]=b,...
  • 二分图的判定匹配问题名词概念匈牙利算法染色法判断二分图-关押罪犯最大匹配-棋盘覆盖最小点覆盖-机器任务最大独立集-骑士放置最小路径重复点覆盖-捉迷藏 概念 什么是二分图? 顾名思义就是能分成两个部分的图 二分图...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,711
精华内容 684
关键字:

染色法判断二分图