ผลต่างระหว่างรุ่นของ "Adt lab/adjlist and bfs"
ไปยังการนำทาง
ไปยังการค้นหา
Jittat (คุย | มีส่วนร่วม) (หน้าที่ถูกสร้างด้วย ': ''This is part of adt lab'' <syntaxhighlight lang="c++"> #include <iostream> #include <vector> #include <list> using namespace ...') |
Jittat (คุย | มีส่วนร่วม) |
||
แถว 1: | แถว 1: | ||
: ''This is part of [[adt lab]]'' | : ''This is part of [[adt lab]]'' | ||
− | <syntaxhighlight lang=" | + | <syntaxhighlight lang="cpp"> |
#include <iostream> | #include <iostream> | ||
#include <vector> | #include <vector> |
รุ่นแก้ไขปัจจุบันเมื่อ 06:50, 1 ธันวาคม 2559
- This is part of adt lab
#include <iostream>
#include <vector>
#include <list>
using namespace std;
#define MAX_N 100000
int n,m;
vector<int> adj[MAX_N];
int deg[MAX_N];
int levels[MAX_N];
void read_input()
{
cin >> n >> m;
for(int i=0; i<n; i++) {
deg[i] = 0;
}
for(int i=0; i<m; i++) {
int u,v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
deg[u]++;
deg[v]++;
}
}
void find_levels(int s)
{
list<int> next_level;
for(int u=0; u<n; u++) {
levels[u] = -1;
}
next_level.push_back(s);
levels[s] = 0;
while(! next_level.empty()) {
list<int> current_level = next_level;
next_level.clear();
for(list<int>::iterator i = current_level.begin();
i != current_level.end(); i++) {
int u = *i;
for(vector<int>::iterator j = adj[u].begin();
j != adj[u].end(); j++) {
int v = *j;
if(levels[v] == -1) {
levels[v] = levels[u] + 1;
next_level.push_back(v);
}
}
}
}
}
main()
{
read_input();
find_levels(0);
cout << levels[n-1] << endl;
}