# 2023/01/15 Mock interview Candidate:阿呀呀
###### tags: `mock interview`

<font size= 4><center> **倒數計時** </center></font>
<iframe id="oak-embed" width="480" height="80" style="display: block; margin: 0px auto; border: 0px;" src="https://embed-countdown.onlinealarmkur.com/zh-tw/#2023-01-15T21:05:00s@Asia%2FTaipei"></iframe>

https://atcoder.jp/contests/abc284/tasks/abc284_e

# 題目講解
time: 20:35

Let K be the number of simple paths (paths without repeated vertices) starting from vertex 1.
Print min(K, 10^6).

n m
4 2
1 2
2 3

path1 = 1
path2 = 1 -> 2
path3 = 1 -> 2 -> 3
K = 3

graph, edges,
each vertex,

find single path
# 作法講解
time: 20:38

ex1:
1
/ \
2 3

path: 1, 1->2, 1->3
ex2:
1
|
2
/ \
3 4

path: 1, 1->2, 1->2->3, 1->2->4
return 4.

1
|
2
/ \
3---4

graph TD;
1---2
2---3
2---4
3---4
4---5

single path: 1,
1->2
1->2->3
1->2->3->4
1->2->3->4->5
1->2->4->3
1->2->4->5
2,3,4

# coding
time: 20:59

void dfs(int node, 
        vector<vector<int>> &adj,
        vector<bool> &visited,
        int &ans,
        int max_cnt)
{
    visited[node] = true;
    ans++;
    if(ans >= max_cnt) {//error
        return;
    }
    for(int next : adj[node]) {
        if(visited[next]) { //mistake
            continue;
        }
        dfs(next, adj, visited, ans, max_cnt); //error!
        if(ans >= max_cnt) {
            return;
        }
    }
    
    visited[node] = false;
}

int get_single_path(int n, vector<vector<int> &edges)
{
    vector<vector<int>> adj(n+1);
    int ans = 0;
    int max_cnt = 1000000;
    vector<bool> visited(n, false);
    //first build adjcent list
    for(vector<int> &e : edges) {
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }
    
    //run dfs
    dfs(1, adj, visited, ans, max_cnt);
    
    return min(ans, max_cnt);//error!
}

# 完成
time: 21:13 (+8)

# Comment
提出的想法都蠻不錯的
但是有點忘記去觀察題目要的output了
ask for hint
之後有清楚意識到題目限制
function小錯 不過實作蠻快速的