1 #include<stack> 2 #include<vector> 3 #include<queue> 4 #include<algorithm> 5  6 using namespace std; 7 #define INF 99999999 8 #define NIL -1 9 int n;10 int g[1000][1000];11 struct Node12 {13     int color;14     int d;            //distance15     int pi;            //pi,ancestor16 }t[1000];17 queue<int> q;18 19 void BFS(int s)20 {21     for (int i=0;i<n;i++)22     {23         if (i!=s)24         {25             t[i].color = 0;26             t[i].d = INF;27             t[i].pi = NIL;28         }29     }30     t[s].color = 1;31     t[s].d = 0;32     t[s].pi = NIL;33     q.push(s);34     while (!q.empty())35     {36         int u = q.front();37         q.pop();38         for (int v=0;v<n;v++)39         {40             if ((g[u][v] == 1)&&(u != v))41             {    42                 if (t[v].color == 0)43                 {44                     t[v].color = 1;45                     t[v].d = t[u].d + 1;46                     t[v].pi = u;47                     q.push(v);48                 }49             }50         }51         t[u].color = 1;52     }53 }54 55 /*56 int main()57 {58     while (cin>>n)59     {60         for (int i=0;i<n;i++)61         {62             for (int j=0;j<n;j++)63             {64                 cin>>g[i][j];65             }66         }67         int s;68         cin>>s;69         BFS(s);70         for (int i=0;i<n;i++)71         {72             cout<<i<<" "<<t[i].d<<" "<<t[i].pi<<endl;73         }74     }75     return 0;76 }77 */