Algorithm-Techniques/DFS & BFS at main · Akhi005/Algorithm-Techniques · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
using namespace std;
bool vis[100000];
int i,k,src,node;
vector<int>grap[10000];
int level[100000];
// To find leaf node'''''''
vector<ll>graph[2000005];
ll cnt[2000005];
void dfs(ll node , ll parent)
{
    if(graph[node].size()==1 && node!=1) cnt[node]=1;
    for(int i: graph[node])
    {
        if(i!=parent)
        {
            dfs(i,node); cnt[node]+=cnt[i];
        }
    }
}
''''''

void dfs(int n){
  vis[n]=1;
  //cout<<n<<' ';
  for(i=0;i<grap[n].size();i++)
  {
      if(vis[grap[n][i]]==0)
         dfs(grap[n][i]);
  }
}
void bfs(int src)
{
   queue<int>q;
    q.push(src);
    while(!q.empty())
    {
        k=q.front();
       // cout<<k<<' '; //node sequence
        q.pop();
        vis[k]=1;
        for(i=0;i<grap[k].size();i++)
        {
            if(vis[grap[k][i]]==0)
            {
                vis[grap[k][i]]=1;
                level[grap[k][i]]=level[k]+1;
                q.push(grap[k][i]);
            }
        }
    }

}
int main()
{
    int i,j,k,m,x,y,node,edge,src;
    cin>>node>>edge;

    for(i=0;i<edge;i++)
    {
        cin>>x>>y;
        grap[x].push_back(y);
        grap[y].push_back(x);
    }
    for(i=0;i<=node;i++) level[i]=0,vis[i]=0;
    cin>>src;
   dfs(src);
   bfs(src);
   for(i=src;i<src+node;i++) cout<<i<<' '<<level[i]<<'\n';//for bfs
}
/*
6 5
1 4
2 4
3 4
4 5
5 6
1
*/