首页 > 代码库 > 染色法判断是否是二分图 hdu2444

染色法判断是否是二分图 hdu2444

2024-07-25 05:16:34   212人阅读

用染色法判断二分图是这样进行的，随便选择一个点，

1.把它染成黑色，然后将它相邻的点染成白色，然后入队列

2.出队列，与这个点相邻的点染成相反的颜色

根据二分图的特性，相同集合内的点颜色是相同的，即

但是如果这个图不是二分图，那么就会这样

把与1相邻的点2,3染成白色，然后入队列，然后2出队列，要把与2相邻的点2,3染成黑色，但是都染过了，所以不用染色

但是3的颜色应该与2相反（如果是二分图的话），可是没有相反，所以就不是二分图

  1 #include <stdio.h>  2 #include <queue>  3 #include <string.h>  4 using namespace std;  5 const int N = 300;  6 struct Edge  7 {  8     int v,next;  9 }g[N*N]; 10 int first[N*N]; 11 int color[N*N]; 12 int cy[N]; 13 bool vis[N]; 14 int e; 15 int n,m; 16 bool is_ ; 17 void addEdge(int a, int b) 18 { 19     g[e].v = b; 20     g[e].next =first[a]; 21     first[a] = e++; 22 } 23 bool bfs(int cur)//染色法，判断是否是二分图 24 {//时间复杂度   邻居矩阵O(n*n)   邻接表 O(n+e) 25     queue<int> q; 26     q.push(cur); 27     color[cur] = 1; 28     while(!q.empty()) 29     { 30         cur = q.front();q.pop(); 31         for(int i=first[cur]; i!=-1; i=g[i].next) 32         { 33             int v = g[i].v; 34             if(color[v] == -1) 35             { 36                 color[v] = 1 - color[cur]; 37                 q.push(v); 38             }     39              40             if(color[v] == color[cur]) 41                 return false; 42         } 43     } 44     return true; 45 } 46 void dfs_color(int cur) 47 { 48     for(int i=first[cur]; i!=-1; i=g[i].next) 49     { 50         int v = g[i].v; 51         if(color[v] == -1) 52         { 53             color[v] = 1 - color[cur]; 54             dfs_color(v); 55         } 56         else if(color[v] == color[cur]) 57             is_ = false; 58          59     } 60  61 } 62 bool dfs(int cur) 63 { 64     for(int i=first[cur]; i!=-1; i=g[i].next) 65     { 66         int v = g[i].v; 67         if(!vis[v]) 68         { 69             vis[v] = true; 70             if(cy[v]==-1 || dfs(cy[v])) 71             { 72                 cy[v] = cur; 73                 return true; 74             } 75         } 76     } 77     return false; 78 } 79 int Match() 80 { 81     int ans = 0; 82     memset(cy, -1, sizeof(cy)); 83     for(int i=1; i<=n; ++i) 84     { 85         memset(vis, 0, sizeof(vis)); 86         ans += dfs(i); 87     } 88     return ans; 89 } 90 int main() 91 { 92     freopen("in.txt","r",stdin); 93     int a,b,i; 94     while(scanf("%d%d",&n,&m)!=EOF) 95     { 96         memset(first, -1, sizeof(first)); 97         e = 0; 98         for(i=0; i<m; ++i) 99         {100             scanf("%d%d",&a,&b);101             addEdge(a,b);102             addEdge(b,a);103         }104         is_ = true;105         memset(color, -1, sizeof(color));106         for(i=1; i<=n; ++i)107         {108             if(color[i] == -1)109             {110                 color[i] = 1;111                 dfs_color(i);112             }113         }114         if(!is_)115             puts("No");116         else117         {118             printf("%d\n",Match()/2);//没有把集合x，y分开，所以相当有2个最大匹配119         }120     }121 }

 

染色法判断是否是二分图 hdu2444


联系
我们