< 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 t eam 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>
์
๋ ฅ ๋ฐ์ ์น๊ตฌ ๊ด๊ณ ๊ฐ์ ์ธ์ ๋ฆฌ์คํธ๋ก ๋ณํํ๋ค.
์น๊ตฌ ๊ด๊ณ์ธ ์ธ์ ๋ฆฌ์คํธ ์ฌ์ด์ฆ๊ฐ k ๋ฏธ๋ง์ด๋ฉด DFS ๋ฅผ ์ด์ฉํ์ฌ ์ฐ๊ฒฐ๋ ๋
ธ๋(๊ตฐ์ธ)๋ค๊ณผ์ ์ฐ๊ฒฐ์ ์ง์ฐ๊ณ ์ฐ๊ฒฐ๋ ๋
ธ๋์ ๋ฆฌ์คํธ ์ฌ์ด์ฆ๊ฐ k ๋ฏธ๋ง์ธ์ง ๋ค์ ํ์ธํ๋ค.
๋ฆฌ์คํธ ์ฌ์ด์ฆ๊ฐ k๋ฏธ๋ง์ด๋ฉด ์ ์์
์ DFS๋ฅผ ํ๊ณ ๋ค๋๋ฉด์ ๋ฐ๋ณตํ๋ค.
๋ง์ฝ ์ฌ๊ธฐ์ ์ธ์ ๋ฆฌ์คํธ ์ฌ์ด์ฆ๊ฐ k๊ฐ ์ด์์ธ ๋
ธ๋๊ฐ ์กด์ฌํ์ง ์๋๋ค๋ฉด 0์ ๋ฆฌํดํ๋ค.
์ธ์ ๋ฆฌ์คํธ ์ฌ์ด์ฆ๊ฐ 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;
}