// 네트워크 플로우
// 네트워크 상에서 최대한 얼마나 많은 양의 유량을 흘려보낼수 있는가를 묻는 알고리즘
// 일반적으로 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);
}
}
