์ด๋ถ ๊ทธ๋ํ
1. ๊ฐ๋
์ด๋ถ ๊ทธ๋ํ๋ ์ธ์ ํ ์ ์ ๋ผ๋ฆฌ ์๋ก ๋ค๋ฅธ ์์ผ๋ก ์น ํ์ฌ ๋ชจ๋ ์ ์ ์ ๋ ๊ทธ๋ฃน์ผ๋ก ๋๋๊ณ , ์๋ก ๋ค๋ฅธ ๊ทธ๋ฃน์ ์ ์ ์ ๊ฐ์ ์ผ๋ก ์ฐ๊ฒฐํ ๊ทธ๋ํ๋ฅผ ๋งํ๋ค.
2. ์ด๋ถ ๋งค์นญ ์๊ณ ๋ฆฌ์ฆ
์ด๋ถ ๋งค์นญ์ด๋ ์ด๋ถ ๊ทธ๋ํ์์ ํ์ชฝ ๊ทธ๋ฃน(A)๊ณผ ๋ค๋ฅธ ํ์ชฝ ๊ทธ๋ฃน(1)์ด ๋งค์นญ์ ํ์ ๋ ์ต๋ ์ ๋์ ๊ตฌํ๋ ๋ฌธ์ ๋ฅผ ๋งํ๋ค.
3. ๋ฌธ์
https://www.acmicpc.net/problem/1707
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
#define RED 1
#define BLUE 2
vector<int> vect[20001];
int visited[20001];
int V, E;
void DFS(int start)
{
// ์ฒ์ ๋ฐฉ๋ฌธํ ์ ์ด๋ฉด RED
if (visited[start] == 0)
visited[start] = RED;
for (int i = 0; i < vect[start].size(); i++)
{
int idx = vect[start][i];
if (visited[idx] == 0) // ์ฐ๊ฒฐ๋ ์ ์ค ๋ฐฉ๋ฌธ ์ํ ์ ์ด๋ฉด
{
visited[idx] = visited[start] == RED ? BLUE : RED; // ๋ฐ๋ ์ ์ผ๋ก ๋ฃ์ด์ฃผ๊ธฐ
DFS(idx);
}
}
}
void BFS(int start)
{
// ์ฒ์ ๋ฐฉ๋ฌธํ ์ ์ด๋ฉด RED
visited[start] = RED;
queue<int> q;
q.push(start);
while (q.size() != 0)
{
int now = q.front();
q.pop();
for (int i = 0; i < vect[now].size(); i++)
{
int idx = vect[now][i];
if (visited[idx] == 0) // ์ฐ๊ฒฐ๋ ์ ์ค ๋ฐฉ๋ฌธ ์ํ ์ ์ด๋ฉด
{
visited[idx] = visited[now] == RED ? BLUE : RED; // ๋ฐ๋ ์ ์ผ๋ก ๋ฃ์ด์ฃผ๊ธฐ
q.push(idx);
}
}
}
}
int check()
{
for (int i = 1; i <= V; i++)
{
for (int j = 0; j < vect[i].size(); j++)
{
int idx = vect[i][j];
if (visited[i] == visited[idx])
return false; // ์ธ์ ํ ๋
ธ๋์ ์์ด ๊ฐ์ผ๋ฉด ์ด๋ถ๊ทธ๋ํ ์๋
}
}
return true;
}
int main()
{
int T;
int u, v;
cin >> T;
while (T--)
{
cin >> V >> E;
for (int i = 0; i < E; i++)
{
cin >> u >> v;
vect[u].push_back(v);
vect[v].push_back(u);
}
// ๋น์ฐ๊ฒฐ ๊ทธ๋ํ๊ฐ ์์ ์๋ ์์ผ๋ฏ๋ก ์ ์ ๋ค ๋ฐฉ๋ฌธ
for (int i = 1; i <= V; i++)
if (visited[i] == 0)
BFS(i);
if (check() == 0)
cout << "NO\n";
else
cout << "YES\n";
memset(visited, 0, sizeof(visited));
memset(vect, 0, sizeof(vect));
}
}
https://www.acmicpc.net/problem/11375
#include <iostream>
#include <vector>
using namespace std;
vector<int> work[1001];
int staff[1001];
bool ck[1001];
bool dfs(int index)
{
if (ck[index])
return false;
ck[index] = true;
for (auto i : work[index])
if (!staff[i] || dfs(staff[i])) {
staff[i] = index;
return true;
}
return false;
}
int main()
{
int N, M;
cin >> N >> M;
for (int i = 1, A, B; i <= N; ++i) {
cin >> A;
while (A--) {
cin >> B;
work[i].push_back(B);
}
}
int ans = 0;
for (int i = 1; i <= N; ++i) {
fill(ck, ck + N, false);
if (dfs(i))
++ans;
}
cout << ans;
}