문제

문제 분석

모든 학생은 2개의 선물을 받아야한다. 그런데 선물은 0, 1, 2, 3...개로 사람마다 다양하게 받을 수 있다.
이때 처음부터 2개 미만의 선물을 받는 사람은 가능성이 전혀 없다. 따라서, 2개 미만의 선물을 받는 사람을 제거해야 한다.
다음은 3 이상을 받는 사람들을 해결해야 한다. 그런데 3개 이상의 선물을 받는 사람이 있다는 것은 누군가 2개 미만을 받았다는 것이다. 2개 미만의 선물을 받는 사람들을 전부 제거하면 3 이상을 받는 사람도 자연스레 사라진다.

알고리즘

아래와 같이 topological sorting 기법으로 순차적으로 학생을 제거하면 된다.

for ( 학생){
	adjList[학생].push_back(상대학생);
	indgree[상대학생]++;
}

queue = indegree < 2 학생; // 제거해야 하는 학생 queue

while (queue!=empty){
	제거학생 = queue.front();
	for ( 상대학생 in adjList[제거학생] ){
    	indegree[상대학생]--;
        if ( indgree[상대학생] < 2 )
        	queue.push( 상대학생 )
    }
}

시간 복잡도는 O(V+E)이다.

자료구조

• adjList: 2차원 vector<vector>
• queue: topological sorting 용 queue
• removed: 제거된 학생 기록용 vector

결과

성공

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int N;

int main(void )
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> N;
    
    vector<vector<int>> directedGraph(N);
    vector<int> indegree(N, 0 );
    {
        int a, b;
        for ( int i = 0; i < N; i++ ){
            cin >> a >> b;
            directedGraph[i].push_back(a-1);
            directedGraph[i].push_back(b-1);
            
            indegree[a-1]++;
            indegree[b-1]++;
        }
    }
    
    queue<int> topologicalQ;
    vector<bool> removedNodes(N, false );
    int removedCount = 0;
    for ( int i = 0; i < N; i++ ){
        if ( indegree[i] < 2 ){
            topologicalQ.push(i);
            removedNodes[i] = true;
            removedCount++;
        }
    }
    while ( topologicalQ.empty() == false ){
        int srcNode = topologicalQ.front();
        topologicalQ.pop();

        for ( int i = 0; i < 2; i++ ){
            int trgNode = directedGraph[srcNode][i];
            indegree[trgNode]--;
            if ( indegree[trgNode] < 2 && removedNodes[trgNode] == false ){
                topologicalQ.push(trgNode);
                removedNodes[trgNode] = true;
                removedCount++;
            }
        }
    }

    cout << (N-removedCount);
    if ( removedCount < N ){
        cout << endl;
        for ( int i = 0; i < N; i++ ){
            if ( removedNodes[i] == false )
                cout << i + 1<< " ";
        }
    }
}

Other

단순하게 stack을 사용하는 위상 정렬로는 어렵다.
indgree를 사용하는 khan's algorithm을 사용해야 했다.