Monk and the Islands | Editorial by destroyerguy

**Explanation:-**
        It is simple level-finding of **bfs**.We will create an adjacency list to store the adjacent neighbours  using **vector stl**  present in C++.Then we will traverse using bfs with 1 as the source node till N and store the level of each node in an array.
        The required minimum number of bridges will be the number of edges in the shortest path from 1 to N which will be equal to level of the Nth node.
** Code:-**
```
                 /*
                    Coded with love by :- Ashutosh Singh
                    Indian Institute Of Information Technology Sricity
                */
                #include<bits/stdc++.h>
                //#include<boost/multiprecision/cpp_int.hpp>
                //using namespace boost::multiprecision;
                using namespace std;
                typedef long long int ll;
                #define mod 1000000007
                #define f(i,n) for(int i=0;i<n;i++)
                #define fp(i,k,n) for(int i=k;i<=n;i++)
                #define fr(i,k,n) for(int i=k;i>=n;i--)
                typedef map<string,int> msi;
                typedef map<string,string> mss;
                vector<int> v[10005];
                int visited[10005];
                int level[10005];
                void bfs(int x)
                {
                    level[x]=0;
                    queue<int> q;
                    q.push(x);
                    visited[x]=1;
                    while(!q.empty())
                    {
                        int p=q.front();
                        q.pop();
                        f(i,v[p].size())
                        {
                            if(visited[v[p][i]]==0)
                                {
                                    level[v[p][i]]=level[p]+1;
                                    visited[v[p][i]]=1;
                                    q.push(v[p][i]);
                                }
                        }
                    }
                }
                int main()
                {
                    int t,n,m;
                    cin >> t;
                    while(t--)
                    {
                        memset(visited,0,sizeof(visited));
                        memset(level,0,sizeof(level));
                        fp(i,1,10004)
                        {
                            v[i].clear();
                        }
                        cin >> n >> m;
                        while(m--)
                        {
                            int x,y;
                            cin >> x >> y;
                            v[x].push_back(y);
                            v[y].push_back(x);
                        }
                        bfs(1);
                        cout << level[n] << '\n';
                    }
                }
```

Monk and the Islands | Editorial by destroyerguy

Download submission

All caught up!

View submission

Is your resume even shortlisted?