Junnnho

// 이분매칭은 네트워크플로우에 연결되는 개념
// DFS를 이용해서 집단과 집단간의 매칭이 "조건대로" + 최대한 이루어지도록 하는 개념

// Max Matching 이라고도 함
// 각 정점을 연결하고, start, end 정점을 각각 만들어서 집단별로 연결시킨 후에
// 그 간선의 유량을 1로 설정하면 네트워크플로우의 개념으로 적용가능

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

#define MAX 100

vector<int> a[MAX];
int d[MAX]; // 특정 정점을 가리키고 있는 정보를 표현
bool c[MAX]; // 정점의 처리 여부

bool dfs(int x) { // matching 이 가능한지 여부를 판단하기 위해 bool type을 사용

	// 연결된 모든 노드에 대해서 들어갈 수 있는지 시도해본다
	for (int i = 0; i < a[x].size(); i++) {
		int t = a[x][i];

		// 이미 처리된 노드는 더이상 볼 필요가 없음
		if (c[t]) continue;
		c[t] = true;

		// 비어있거나 점유노드가 다른 곳에 매칭될 수 있는 경우
		if (d[t] == 0 || dfs(d[t])) {
			d[t] = x;
			return true;
		}
	}

	return false;
}

int main() {
	int answer = 0; // answer 는 이분매칭을 통해 최대한 만족하는 매칭의 갯수를 의미

	for (int i = 1; i <= MAX; i++) {
		fill(c, c + MAX, false); // 매 탐색마다 처리된 노드를 초기화해줌
		if (dfs(i)) answer++;
	}
}

// 네트워크 플로우

// 네트워크 상에서 최대한 얼마나 많은 양의 유량을 흘려보낼수 있는가를 묻는 알고리즘
// 일반적으로 BFS를 이용한 에드몬드 카프 알고리즘을 이용한다
// 에드몬드 카프 알고리즘은 음의 유량을 반드시 고려해주어야 한다
// 플로우의 경우 순서는 상관없다
// 최대유량은 시작점에서 나가는 유량 == 도착점에서 들어오는 유량

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;

#define MAX 10001
#define inf 987654321

int N;
ll cp[MAX][MAX], flow[MAX][MAX], pre[MAX]; // cp : capacity, flow : flow, pre : previous visit now
vector<int> v[MAX]; // 서로 연결된 정점

ll maxflow(int start, int end) {
	queue<int> q;
	ll ret = 0; // ret is maximum flow(answer)

	while (1) { // end 정점에 방문하지 못했다면 계속적으로 반복한다

		while (!q.empty()) q.pop();
		memset(pre, -1, sizeof(pre)); // 방문배열을 초기화!
		q.push(start);

		while (!q.empty()) {
			int num = q.front();
			q.pop();
			if (num == end) break; // 만약 끝정점에 도달했다면 탐색끝

			for (int i = 0; i < v[num].size(); i++) {
				// 흐를 수 있는 유량이 있고, 이 노드를 방문하지 않았다면
				if (cp[num][v[num][i]] - flow[num][v[num][i]] > 0 && pre[v[num][i]] == -1) {

					q.push(v[num][i]), pre[v[num][i]] = num;
				}
			}
		}
		if (pre[end] == -1) break;

		ll min_flow = inf; // 가장 많이 흐를 수 있는 유량을 확인하기 위해 INF로 초기화해서 min으로 값을 맞춰간다
		for (int i = end; i != start; i = pre[i]) {
			min_flow = min(min_flow, cp[pre[i]][i] - flow[pre[i]][i]);
		}
		for (int i = end; i != start; i = pre[i]) {
			flow[pre[i]][i] += min_flow; // 현재 노드에서 다음 노드로 흐르는 유량은 + 처리를 해준다
			flow[i][pre[i]] -= min_flow; // 다음 노드에서 현재 노드로 흐르는 유량은 - 처리를 해준다
		}
		ret += min_flow;// ret는 최대유량으로, min_flow를 계속 더해주면 된다
	}

	return ret;
}

int main() {

	while (1) {
		// a <-> b 를 서로 연결해준다
		v[a].push_back(b);
		v[b].push_back(a);
		// 용량은 양쪽으로 흐르기 때문에 a<->b 방향 모두 += w 처리를 해준다
		cp[a][b] += w;
		cp[b][a] += w;
	}
	
    maxflow(start, end);
}

// 위상정렬
// 순서가 정해져있는 작업을 차례대로 수행해야 할 때 사용
// non cycle & direct graph

// 알고리즘 순서
// 진입차수 : 한 정점으로 들어오는 다른 정점의 갯수
// 1. 진입차수가 0인 정점을 queue에 삽입
// 2. queue에서 정점을 꺼내 연결된 모든 간선을 제거
// 3. 간선 제거 이후에 진입차수가 0이 된 정점을 다시 queue에 넣어준다 ==> 항상 진입차수가 0인 정점만 큐에 삽입한다
// 4. 2,3번을 반복, 모든 정점을 방문하기 전에 queue가 빈다면 사이클이 존재하는 것이고, 모든 정점을 방문했다면 queue에서 꺼낸 순서가 위상정렬의 순서

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

#define MAX 10

int n, inDegree[MAX]; // inDegree : 진입차수를 의미
vector<int> a[MAX];

void wsort() {
	int result[MAX];
	queue<int> q;

	//진입 차수가 0인 노드를 queue에 삽입
	for (int i = 1; i <= n; i++) {
		if (inDegree[i] == 0) q.push(i);
	}

	//위상 정렬이 완전히 수행하려면 정확히 N개의 노드를 방문
	for (int i = 1; i <= n; i++) {
		// N개를 방문하기 전에 queue가 빈다면 사이클이 발생 -> 위상정렬 불가능
		if (q.empty()) return;

		int x = q.front();
		q.pop();
		result[i] = x; // queue에서 꺼낸 x는 위상정렬의 순서를 지키고 있는 노드
		for (int i = 0; i < a[x].size(); i++) {
			int y = a[x][i];
			if (--inDegree[y] == 0) q.push(y); // 진입을 제거해주고 차수가 0이면 queue에 삽입
		}
	}

	// 순서 출력
	for (int i = 1; i <= n; i++) {
		printf("%d ", result[i]);
	}
}

// SCC strong connected component
// 방향 그래프일때만 고려가능하다
// 사이클이 발생하는 경우 무조건 SCC에 해당한다
// 타잔(tarjan)알고리즘
// 모든 정점에 대해서 DFS를 수행해서 SCC를 찾는다
// 한 정점에서 출발해서 다시 출발 정점으로 돌아올 수 있는 경로에 한해서 SCC가 존재한다

// DFS 중에 발견한 정점이 스택내에 들어가있다면 이 정점이 나의 부모정점이다 라는 의미가 된다
// 이때부터 리턴을 하다가 자기 자신과 부모가 같은 정점으로 되돌아오면 출발 정점이 됨을 의미한다
// 부모값이 자신보다 더 작은 값으로 갱신되면서 부모정점으로 되돌아가게 되는 탐색

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
#define MAX 10000

bool finished[MAX]; // 현재 특정한 노드에 대한 DFS가 끝났는지 확인
int id, d[MAX]; // id : 각 노드마다 고유한 번호를 할당할 변수, d : 정점마다 할당된 번호를 담기 위함
vector<int> a[MAX];
vector<vector<int> > SCC;
stack<int> s;

// DFS는 총 정점의 갯수만큼 실행
int dfs(int x) {
	d[x] = ++id; // 노드마다 고유한 번호를 할당 (맨처음 부모로 설정된 값)
	s.push(x);

	int parent = d[x]; // 초기에는 id 자체를 고유 번호로 지정

	for (int i = 0; i < a[x].size(); i++) {
		int y = a[x][i]; // x와 연결된 정점 y

		// ** 더 작은 값으로 부모를 가리키도록 탐색한다 **

		// 해당노드를 방문한 적이 없다면 dfs를 수행
		if (d[y] == 0) parent = min(parent, dfs(y));
		// 방문은 했는데 처리가 끝나지 않은 정점이라면
		else if (!finished[y]) parent = min(parent, d[y]);
	}
	
	// 부모노드가 자기 자신인 경우
	if (parent == d[x]) {
		// 스택에서 자기자신이 나올떄까지 뽑아서 SCC에 저장
		vector<int> scc;
		while (1) {
			int t = s.top();
			s.pop();
			scc.push_back(t);
			finished[t] = true; // 처리완료됨을 의미
			if (t == x) break; // 자기자신을 만나면 종료
		}
		SCC.push_back(scc);
	}

	return parent;
}

int main() {

	int N; // N is node_cnt

	// for dfs i 1 to N
	for (int i = 1; i <= N; i++) {
		// check ths not visit node
		if (d[i] == 0) dfs(i);
	}

}