1154 Vertex Coloring (25 分)

2024-03-04 16:32

文章标签 25 1154 vertex coloring

本文主要是介绍1154 Vertex Coloring (25 分)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

版本2

图的深搜

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include <queue> 
#include <unordered_set>
#include <algorithm>
using namespace std;
const int N = 1e4+5;
vector<int> G[N];
bool vis[N]; 
int n, m;
int color[N];
bool flag;
void dfs(int r){ if(flag) return; //如果着色冲突则返回 vis[r] = true;for(int i = 0; i < G[r].size(); i++){int v = G[r][i];if(color[r] == color[v]) flag = true;if(flag) return; if(!vis[v]) dfs(v);}
}
int main(){scanf("%d%d", &n, &m);int u, v;while(m--){scanf("%d%d", &u, &v);G[u].push_back(v);G[v].push_back(u); //无向图 }int k;scanf("%d", &k);while(k--){unordered_set<int> st;flag = false;for(int i = 0; i < n; i++) scanf("%d", color+i), st.insert(color[i]);memset(vis, 0, sizeof vis);for(int i = 0; i < n; i++){if(!vis[i]) dfs(i);}if(!flag) printf("%d-coloring\n", st.size());else puts("No");}return 0;
}

版本1

遍历所有边，不需要用深搜，只需要把读入的每条边再循环一遍就ok了

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;
int arr[maxn];
struct node{int u,v;
}E[maxn];set<int> st;int main(){int n,m,u,v;scanf("%d%d",&n,&m);for(int i=0; i<m; i++){scanf("%d%d",&u,&v);E[i].u = u;E[i].v = v;}int k;scanf("%d",&k);while(k--){memset(arr,-1,sizeof(arr));st.clear();for(int i=0;i<n;i++){scanf("%d",&arr[i]);st.insert(arr[i]); }int flag=0;for(int i=0;i<m;i++){if(arr[E[i].u] == arr[E[i].v]){flag=1;break;}}if(flag){printf("No\n");}else printf("%d-coloring\n",st.size());}return 0;
}