首页 > 代码库 > Codeforces 501C Misha and Forest(bfs)
Codeforces 501C Misha and Forest(bfs)
题目链接:http://codeforces.com/problemset/problem/501/C
题意:
思路:
代码:
#include <iostream>#include <stdio.h>#include <cstring>#include <queue>#include <set>#include <cmath>#include <time.h>#include <cstdlib>#include <algorithm>#define lson (i<<1)#define rson (lson|1)using namespace std;typedef long long LL;const int N = 1000007;const int INF = 0x7fffffff;struct Node{ int idx; int de; int val;}dt[N];struct Ans{ int a, b;}ans[N];int n, vis[N], cnt_ans;void bfs(){ queue<int> que; for (int i = 0; i < n; i++) { if (dt[i].de == 1) { vis[i] = 1; que.push(i); } } while (!que.empty()) { int t = que.front(); que.pop(); struct Node temp = dt[t]; if (dt[temp.idx].de == 0) continue; ans[cnt_ans].a = temp.idx; ans[cnt_ans].b = temp.val; cnt_ans++; dt[temp.val].de--; dt[temp.val].val ^= temp.idx; if (dt[temp.val].de == 1 && !vis[temp.val]) { vis[temp.val] = 1; que.push(temp.val); } }}int main(){ ios_base::sync_with_stdio(0); cin.tie(0); while (cin >> n) { cnt_ans = 0; memset(vis, 0, sizeof(vis)); for (int i = 0; i < n; i++) { dt[i].idx = i; cin >> dt[i].de >> dt[i].val; if (dt[i].de == 0) vis[i] = 1; } bfs(); cout << cnt_ans << endl; for (int i = 0; i < cnt_ans; i++) cout << ans[i].a << " " << ans[i].b << endl; } return 0;}
Codeforces 501C Misha and Forest(bfs)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。