Algorithms/BFS.cpp at master · abdullah-sust/Algorithms · 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
//undirected graph
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
queue<int>Q;
int arr[1000][1000],dis[1000],vis[1000];
void bfs(int start,int end)
{
    int i,u;
    while(!Q.empty())
    Q.pop();
    Q.push(start);
    vis[start]=1;
    dis[start]=0;
    while(!Q.empty())
    {
        u=Q.front();
        Q.pop();
        for(i=1;i<=end;++i)
        if(vis[i]==0&&arr[u][i]==1)
        {
            vis[i]=1;
            dis[i]=dis[u]+1;
            Q.push(i);
        }
    }
    return ;
}
int main()
{
    int p,d,i,m,n,x,y;
    while(scanf("%d %d",&p,&d)==2)
    {
        memset(arr,0,sizeof(arr));
        memset(dis,-1,sizeof(dis));
        memset(vis,0,sizeof(vis));
        for(i=0;i<d;++i)
        {
            scanf("%d %d",&m,&n);
            arr[m][n]=arr[n][m]=1;
        }
        bfs(1,p);
        printf("Level for all nodes is: ");
            for(i=1;i<=p;++i)
            printf(" %d",dis[i]);
        printf("\n\n");
    }
    return 0;
}
/*
Input:
6 7
1 2
2 3
3 6
6 5
5 4
4 1
2 5
Output:
0 1 2 1 2 3
*/