2015年1月19日 星期一

Codeforces Round #285 (Div. 1), problem: (A) Misha and Forest

給定每個點的degree, sigma_xor adj_index,找出原圖
一直戳degree = 1的點

#include<cstdio>
#include<cstdlib>
#include<vector>
#include<queue>
#include<utility>

using namespace std;

int deg[1000000];
int val[1000000];
int que[1000000];

int main(){
    int n; scanf("%d", &n);
    for(int lx = 0;lx < n;lx++)
        scanf("%d %d", deg + lx, val + lx);
    int qs = 0, qe = 0;
    for(int lx = 0;lx < n;lx++)
        if(deg[lx] == 1)
            que[qe++] = lx;
    vector<pair<int,int> > ans;
    while(qe > qs){
        int prc = que[qs++];
        if(deg[prc] < 1) continue;
        int to = val[prc];
        ans.push_back(pair<int,int>(prc, to));
        val[to] ^= prc;
        deg[to]--;
        if(deg[to] == 1) 
            que[qe++] = to;
    }
    printf("%d\n", (int)ans.size());
    for(int lx = 0;lx < ans.size();lx++){
        printf("%d %d\n", ans[lx].first, ans[lx].second);
    }
    return 0;
}

沒有留言:

張貼留言