首页 > 代码库 > 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)