hdu4751Divide Groups(dfs枚举完全图集合或者bfs染色)

本文涉及的产品
传统型负载均衡 CLB,每月750个小时 15LCU
应用型负载均衡 ALB,每月750个小时 15LCU
EMR Serverless StarRocks,5000CU*H 48000GB*H
简介:

/*************************************************************************
    > File Name: j.cpp
    > Author: HJZ
    > Mail: 2570230521@qq.com 
    > Created Time: 2014年08月28日 星期四 12时26分13秒
 ************************************************************************/

//提議:能否將一個給定的有向圖,變成兩個完全圖(任意兩點都直接相連,雙向邊)

#include <queue>
#include <string>
#include <cstdio>
#include <stack>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 105
using namespace std;

int a[N], b[N];
//a, b集合初始化爲空!
int g[N][N];
int n;

bool flag;

bool dfs(int u, int la, int lb){
   if(u>n && la+lb==n) return true;//如果a ,b集合中的元素數目恰好是n,則說明可以形成兩個完全圖!
   bool flagx=true;
   for(int i=0; i<la && flagx; ++i)
       if(!(g[a[i]][u] && g[u][a[i]]))
           flagx=false;
   if(flagx) a[la]=u;//如果u節點可以放入a集合中
   if(flagx && dfs(u+1, la+1, lb)) return true;
   bool flagy=true;
   for(int i=0; i<lb && flagy; ++i)
       if(!(g[b[i]][u] && g[u][b[i]]))
            flagy=false;
   if(flagy) b[lb]=u;//如果u節點可以放入b集合中
   if(flagy && dfs(u+1, la, lb+1)) return true;
   return false;
}

int main(){
   while(scanf("%d", &n)!=EOF){
      memset(g, 0, sizeof(g));
      for(int i=1; i<=n; ++i){
         int v;
         vis[i]=0;
         while(scanf("%d", &v) && v)
           g[i][v]=1;
      }
     flag=dfs(1, 0, 0);
     if(flag)
         printf("YES\n");
     else printf("NO\n");
   }
   return 0;
}
/*************************************************************************
    > File Name: j.cpp
    > Author: HJZ
    > Mail: 2570230521@qq.com 
    > Created Time: 2014年08月28日 星期四 12时26分13秒
 ************************************************************************/
//思路:bfs,和判断二分图差不多,将图分成两个集合,如果a和b都有g[a][b]&&g[b][a]说明
//a和b一定在同一个集合中,如果有a,b不在一个集合中,a,c不在同一个集合中,b,c也不在同一个
//集合中,出现矛盾!也就是这个图不能分成两个完全图!
#include <queue>
#include <string>
#include <cstdio>
#include <stack>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 105
using namespace std;
queue<int>q;
int g[N][N];
int coll[N];
int n;

bool bfs(int u){
    while(!q.empty())  q.pop();
    q.push(u);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int y=1; y<=n; ++y){
           if(x==y || g[x][y]&&g[y][x]) continue;
           if(coll[y]==-1){
                coll[y]=coll[x]^1;
                q.push(y);
           }
           else if(coll[y]==coll[x])
                return true;
        }
    }
    return false;
}

int main(){
   while(scanf("%d", &n)!=EOF){
       memset(g, 0, sizeof(g));
       for(int i=1; i<=n; ++i){
            int v;
            while(scanf("%d", &v) && v)
                g[i][v]=1;
            coll[i]=-1;
       }
       int i;
       for(i=1; i<=n; ++i){
           if(coll[i]==-1){
               coll[i]=0;//默认是在集合0中
               if(bfs(i)) break;
           }
       }
       if(i<=n) printf("NO\n");
       else printf("YES\n");
   }
   return 0;
}

相关实践学习
SLB负载均衡实践
本场景通过使用阿里云负载均衡 SLB 以及对负载均衡 SLB 后端服务器 ECS 的权重进行修改,快速解决服务器响应速度慢的问题
负载均衡入门与产品使用指南
负载均衡(Server Load Balancer)是对多台云服务器进行流量分发的负载均衡服务,可以通过流量分发扩展应用系统对外的服务能力,通过消除单点故障提升应用系统的可用性。 本课程主要介绍负载均衡的相关技术以及阿里云负载均衡产品的使用方法。
目录
相关文章
|
Java
hdu1016 Prime Ring Problem【素数环问题(经典dfs)】
hdu1016 Prime Ring Problem【素数环问题(经典dfs)】
47 0
|
人工智能
CF1315 C.Restoring Permutation(构造 二分 贪心)
CF1315 C.Restoring Permutation(构造 二分 贪心)
67 0
UPC Graph (最小生成树 || 并查集+二分)
UPC Graph (最小生成树 || 并查集+二分)
92 0
|
算法 Go C++
UPC Go Home(贪心 || 前缀和+二分)(STL二分函数的使用)
UPC Go Home(贪心 || 前缀和+二分)(STL二分函数的使用)
86 0
|
测试技术
输出全排列 (20 分)(dfs模板题)
输出全排列 (20 分)(dfs模板题)
106 0
Biggest Number深搜
You can start from any square, walk in the maze, and finally stop at some square. Each step, you may only walk into one of the four neighbouring squares (up, down, left, right) and you cannot walk into obstacles or walk into a square more than once.
113 0
Biggest Number深搜
|
并行计算 测试技术 容器
【LeetCode128】最长连续序列(unordered_map+dfs-记忆化搜索)
初级解法:用sort排序和用unique去重后for循环遍历一遍数组,如果当前和上一个数字之差为1,则count累加1;如果当前数字和上一个数字之差不为1,则重新设count为1计算。
111 0
【LeetCode128】最长连续序列(unordered_map+dfs-记忆化搜索)
HDU-1598,find the most comfortable road(并查集+枚举)
HDU-1598,find the most comfortable road(并查集+枚举)