---
# System prepended metadata

title: '2023/01/15 Mock interview Candidate:阿呀呀'
tags: [mock interview]

---

# 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
  
```mermaid
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
```cpp=

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小錯 不過實作蠻快速的