# week7 note

## 數字全排列

#include <bits/stdc++.h>
using namespace std;

int n = 3, m = 2;//n = 3, m = 2
vector<int> v;//vector 的名字是 v

void dfs(int lev, int num) {//召喚dfs
	if(lev == m) {
		for(int t : v) cout << t << ' ';
		cout << endl;//換行
		return;
	}
	
	for(int i = num + 1; i <= n; i++) {
		v.push_back(i);
		dfs(lev + 1, i);
		v.pop_back();
	}
	
}

int main() {
	dfs(0, 0);
}

## DFS 判斷 $node_0$ 可不可以走到 $node_{n-1}$

輸入n, m 分別為點的個數(idx為0~n-1), 邊的個數
接下來有m行，每行有兩個數字u, v，代表u可以到v
保證輸入沒有環

$n <= 100$

範例輸入
7 8
0 1
1 2
1 3
2 4
4 0
2 6
5 6
6 4

範例輸出
YES

#include <bits/stdc++.h>
using namespace std;

int G[105][105] {};
bool visit[105];
int n;

void dfs(int idx) {
    if(visit[idx]) return;
    visit[idx] = 1;
    
    
    for(int i = 0; i < n; i++) { //每次新的idx對全部的數字搜尋有沒有路
        if(G[idx][i] == 1) { //如果某一條有路以新數作為idx往下
            dfs(i);
        }
    }
}

int main() {
    int m;
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        G[u][v] = 1;
    }
    dfs(0);
    if(visit[n-1]) cout << "YES\n";
    else cout << "NO\n";
}

## dfs 找到 0 ~ n-1 的所有路徑
輸入和前面一樣
7 8
0 1
1 2
1 3
2 4
0 4
2 6
6 5
6 4

#include <bits/stdc++.h>
using namespace std;

int G[105][105] {};
bool visit[105];
int n;
vector<int> path;

void dfs(int idx) {
	if(idx == n-1) {
		for(int u : path) cout << u << ' ';
		cout << endl;
	}
	for(int i = 0; i < n; i++) if(G[idx][i] == 1) {
		path.push_back(i);
		dfs(i);
		path.pop_back();
	}
}

int main() {
	int m;
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		G[u][v] = 1;
	}
	dfs(0);
}

## 給你一張圖判斷是不是樹
=> 找看看有沒有環
=> dfs如果走到父節點以外重複的點，就是有環!!

bool circle = false;
void dfs(int idx) {
    if(visit[idx]) circle = true;
    // your code
}

## 找樹的深度

int depth[105]{};
void dfs(int lev, int idx) {
    depth[idx] = lev;
    .
    .
        dfs(lev + 1, i)
    .
}

## 找子樹大小(以x為根結點的子樹節點樹)

const int maxn = 1e5 + 50; 
vector<int> G[100005];
bool visit[105];
int subtree_size[maxn];

void dfs(int idx, int par) {
	subtree_size[idx] = 1;
	for(int u : G[idx]) if(u != par){
		dfs(u);
		subtree_size[idx] += subtree_size[u];
	}
}