Find Edge List [CSAcademy #56 C]

https://csacademy.com/contest/round-56/task/find-edge-list/statement/

N頂点M辺の無向グラフの隣接配列が与えられる。
このとき、隣接配列が与えられたものになるように辺の順番を適切に並べて答えよ。

rep(i,0,M) {
    int x, y; cin >> x >> y;
    E[x].push_back(y);
    E[y].push_back(x);
}

のように追加して、隣接行列を作っていくことを想定する。

解法

隣接行列の頭から貪欲に辺を確定させていく。
例1であれば

N = 5
1| 2 3 4
2| 1
3| 4 1 5
4| 3 1
5| 3
↓ (2,1)が取れるので取る
1| 3 4
2| 
3| 4 1 5
4| 3 1
5| 3
↓ (3,4)が取れるので取る
1| 3 4
2| 
3| 1 5
4| 1
5| 3
↓ (1,3)が取れるので取る
1| 4
2| 
3| 5
4| 1
5| 3
↓ (1,4)が取れるので取る
1|
2| 
3| 5
4|
5| 3
↓ (5,3)が取れるので取る
1|
2| 
3|
4|
5|

という感じ。途中で取れなくなったら"-1"
　
どう実装するかだが、キューを使って取れる辺を指定していく。
que := 取り除ける辺の集合
idx[i] := 頂点iから何個既に取ったか(または、頂点iから取れる辺の先頭の添字)
頂点i,jについて
j = E[i][idx[i]]
E[j][idx[j]] = i
を満たせば、辺(i,j)は取ることができる。
　
これをバグらせないように実装し切るとAC

int N, M;
vector<int> E[101010];
int idx[101010];
vector<pair<int, int>> ans;
set<pair<int, int>> done;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) {
        int K; cin >> K;
        rep(j, 0, K) {
            int x; cin >> x; x--;
            E[i].push_back(x);
        }
        M += K;
    }
    M /= 2;

    queue<pair<int, int>> que;

    rep(i, 0, N) if(E[i].size()) {
        int j = E[i][0];
        if (E[j].size()) if (E[j][0] == i) que.push({ i, j });
    }

    while (!que.empty()) {
        auto q = que.front(); que.pop();

        int x = q.first;
        int y = q.second;

        if (done.count({ min(x,y), max(x,y) })) continue;
        done.insert({ min(x,y), max(x,y) });

        ans.push_back(q);
        
        idx[x]++;
        idx[y]++;

        if (idx[x] < E[x].size()) {
            int a = x;
            int b = E[x][idx[x]];
            if (idx[b] < E[b].size()) if (E[b][idx[b]] == a) que.push({ a, b });
        }
        if (idx[y] < E[y].size()) {
            int a = y;
            int b = E[y][idx[y]];
            if (idx[b] < E[b].size()) if (E[b][idx[b]] == a) que.push({ a, b });
        }
    }

    if (ans.size() < M) printf("-1\n");
    else fore(p, ans) printf("%d %d\n", p.first + 1, p.second + 1);
}