首页 > 代码库 > codeforces #285 div.2 C. Misha and Forest
codeforces #285 div.2 C. Misha and Forest
题目链接: http://codeforces.com/contest/501/problem/C
题意: 给出图的每个顶点的度数和相邻顶点的异或值的和,求出这个图的边的情况和边的数目:
分析: 找出度为一的点,其所对应的异或值即为与之相邻的顶点(<- ^ ->),再将与之相邻顶点的度数减一:
**********代码:
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<queue> using namespace std; const int maxn=1<<16+5; int du[maxn],ytot[maxn]; vector< pair<int ,int > > V; int main() { int n,u,v; int i; while(scanf("%d",&n)!=EOF) { queue<int> Q; for(i=0;i<n;i++) V.clear(); for(i=0;i<n;i++) scanf("%d%d",&du[i],&ytot[i]); for(i=0;i<n;i++) if(du[i]==1) Q.push(i); while(!Q.empty()) { u=Q.front(); Q.pop(); if(du[u]!=1) continue; v=ytot[u]; V.push_back(make_pair(u,v)); du[v]--; ytot[v]^=u; if( du[v]==1) Q.push(v); } printf("%d\n",V.size()); for(i=0;i<V.size();i++) printf("%d %d\n",V[i].first,V[i].second); } return 0; }
codeforces #285 div.2 C. Misha and Forest
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。