图论/位运算 Codeforces Round #285 (Div. 2) C. Misha and Forest

题目传送门

 /*
题意:给出无向无环图,每一个点的度数和相邻点的异或和(a^b^c^....)
图论/位运算:其实这题很简单。类似拓扑排序,先把度数为1的先入对,每一次少一个度数
关键在于更新异或和,精髓:a ^ b = c -> a ^ c = b, b ^ c = a;
*/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std; const int MAXN = 7e4 + ;
const int INF = 0x3f3f3f3f;
int ans[MAXN][];
int d[MAXN], s[MAXN]; int main(void) //Codeforces Round #285 (Div. 2) C. Misha and Forest
{
// freopen ("C.in", "r", stdin); int n;
while (scanf ("%d", &n) == )
{
queue<int> Q;
for (int i=; i<n; ++i)
{
scanf ("%d%d", &d[i], &s[i]);
if (d[i] == ) Q.push (i);
} int cnt = ;
while (!Q.empty ())
{
int u = Q.front (); Q.pop ();
if (d[u] == ) continue;
int v = s[u];
ans[++cnt][] = u; ans[cnt][] = v;
if ((--d[v]) == ) Q.push (v);
s[v] = s[v] ^ u;
} printf ("%d\n", cnt);
for (int i=; i<=cnt; ++i)
{
printf ("%d %d\n", ans[i][], ans[i][]);
}
} return ;
}
上一篇:Codeforces Round #443 (Div. 2) C 位运算


下一篇:string模块