[PPS] Task Force (C++)

< Problem >

The Marine Corps wants to form a special task-force team for a critical mission. The team members are selected from their soldiers. The Marine Corps made the following member selection rule for a strong fellowship among the team members: every member of the special force team has at least 𝑘 friends in the special force team.

 

Given the friendship relations between the soldiers, write a program that finds the maximum size of the special task-force team that satisfies this rule.

For example, suppose that there are 5 soldiers, and their friendship relations are represented as a graph shown above: a node represents a soldier and an edge the friendship between a pair of soldiers. For 𝑘 =2, there are 3 teams that satisfy the rule, that is, {2,3,4

}, {2,4,5} and {2,3,4,5}. Hence, the answer is 4, which is the maximum number of team members over all possible teams satisfying the rule. For 𝑘 is 3, no team satisfies the rule.

 

 

< Requirements >
Input Data

• The first line from the standard input has three integers 𝑛, 𝑘, and 𝑓, where 𝑛 is the number of soldiers, 𝑘 is the minimum number of friends that a soldier must have to join the team, and 𝑓 is the total number
  of friendship relations, for 1≤𝑘 <𝑛≤2000 and 1≤𝑓 ≤𝑛(𝑛−1). The soldiers have IDs from 1 to 𝑛.
• Each of the next 𝑓 lines contains two integers that represent the IDs of two soldiers who are in a friendship.

Output Data

• Your program should print out the maximum size (an integer) of the special task-force team to the standard output.
• If there are no teams that satisfy the rule, print out 0 to the standard output.
• Your program should return the result within 0.5 seconds.

 

 

<Problem Analysis>

 n 명의 해군들 중 특수팀 내에 k명 이상의 친구를 가진 해군들로만 특수팀을 꾸린다. 특수팀에 들어갈 수 있는 최대 인원을 구하라

-> 특수팀 내에 k 명 이상의 친구 관계를 가지고 있어야 한기에, k 명 이상의 친구가 없는 사람들을 배제하고 생각한다. 

 

<Solution>

1. 입력 받은 친구 관계 값을 인접리스트로 변환한다. 
2. 친구 관계인 인접 리스트 사이즈가 k 미만이면 DFS 를 이용하여 연결된 노드(군인)들과의 연결을 지우고 연결된 노드의 리스트 사이즈가 k 미만인지 다시 확인한다. 
3. 리스트 사이즈가 k미만이면 위 작업을 DFS를 타고 다니면서 반복한다. 
4. 만약 여기서 인접리스트 사이즈가 k개 이상인 노드가 존재하지 않는다면 0을 리턴한다. 
5. 인접리스트 사이즈가 k개 이상인 노드들의 개수가 정답이 된다. 

<Asymptotic time complexity>

n = soldiers (노드) , r = relations

∴ O(n) + O(r) + O(n) =  O(n + r) 

 

<Code>

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Graph {
public:
    int N;
    vector<vector<int> > adj;

    Graph(int vertices) {
        N = vertices + 1; 
        adj.resize(N);
    }

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int DFS(int start, int k) {
        vector<bool> visited(N, false);
        queue<int> s;
        queue<int> head;
        int count = 0;

        for (int i=1; i<=start; i++) {
            s.push(i);
        }

        while (!s.empty()) {
        
            int vertex = s.front();
            s.pop();

            if (!visited[vertex]) {
                visited[vertex] = true;

                int next_vertex = -1;  // 다음 노드를 저장할 변수

                if (adj[vertex].size() < k) {
                    if (adj[vertex].size() == 0) continue;

                    for (int i = 0; i < adj[vertex].size(); i++) {
                        int neighbor = adj[vertex][i];
                        removeFriend(neighbor, vertex);

                        if (adj[neighbor].size() < k) {
                            visited[neighbor] = false;
                            s.push(neighbor);
                        }
                    }
                    adj[vertex].clear();
                }
            }
        }

        for (int i=1; i<=start; i++) {
           if (adj[i].size() != 0) {
               count++;
           }
        }

        return count;
    }

    void removeFriend(int vertex, int head) {
        for (int i = 0; i < adj[vertex].size(); i++) {
        	if (adj[vertex][i] == head) {
            	adj[vertex].erase(adj[vertex].begin() + i);
                 break;
            }
        }
    }
};

int main() {
    int soldiers = 0;
    int k = 0;
    int relation = 0;
    int a, b;

    cin >> soldiers >> k >> relation;

    Graph g(soldiers); 

    for (int i = 0; i < relation; i++) {
        cin >> a >> b;
        g.addEdge(a, b);
    }
  
    int specialTeam = g.DFS(soldiers, k);
    cout << specialTeam << endl;

    return 0;
}