首页 > 代码库 > uva 11396Claw Decomposotion(二分图判定)
uva 11396Claw Decomposotion(二分图判定)
题目大意:给出一个简单无向图。每一个点的度为3。推断是否能将此图分解成若干爪的形式,使得每条边都仅仅出如今唯一的爪中。
(点能够多次出如今爪中)
这道题实质上就是问这个图是否为二分图,dfs判定就可以
#include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<iostream> #include<algorithm> #include<vector> #include<map> #include<queue> #include<stack> #include<string> #include<map> #include<set> #define eps 1e-6 #define LL long long using namespace std; const int maxn = 300 + 5; const int INF = 0x3f3f3f3f; vector<int> G[maxn]; //dfs给二分图进行黑白二着色,用颜色1表示黑色,颜色2表示白色,0表示没着色 int color[maxn]; //推断节点u所在的连通分量是否为二分图 int n; bool bipartite(int u) { for(int i = 0; i < G[u].size(); i++) { int v = G[u][i]; if(color[v] == color[u]) return false; if(!color[v]) { color[v] = 3 - color[u]; if(!bipartite(v)) return false; } } return true; } void init() { memset(color, 0, sizeof(color)); for(int i = 1; i <= n; i++) G[i].clear(); int x, y; while(scanf("%d%d", &x, &y) == 2 && x) { G[x].push_back(y); G[y].push_back(x); } } void solve() { color[1] = 1; if(bipartite(1)) puts("YES"); else puts("NO"); } int main() { //freopen("input.txt", "r", stdin); while(scanf("%d", &n) == 1 && n) { init(); solve(); } return 0; }
uva 11396Claw Decomposotion(二分图判定)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。