Algo lab/read graph and bfs - ประวัติรุ่นแก้ไข

Jittat เมื่อ 06:55, 26 มกราคม 2569

2026-01-26T06:55:22Z

Jittat เมื่อ 03:47, 5 พฤศจิกายน 2563

2020-11-05T03:47:56Z

Jittat เมื่อ 03:47, 5 พฤศจิกายน 2563

2020-11-05T03:47:18Z

Jittat: /* First version */

2020-11-05T03:43:28Z

First version

Jittat: สร้างหน้าด้วย "== First version == #include #include using namespace std; const int MAX_N = 100010; int m,n; vector<..."

2020-11-05T03:41:28Z

สร้างหน้าด้วย "== First version == <syntaxhighlight lang="cpp"> #include <iostream> #include <vector> using namespace std; const int MAX_N = 100010; int m,n; vector<..."

หน้าใหม่

== First version ==
<syntaxhighlight lang="cpp">
#include <iostream>
#include <vector>

using namespace std;

const int MAX_N = 100010;

int m,n;
vector<int> adj[MAX_N];
int deg[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; u--; v--;

adj[u].push_back(v);
adj[v].push_back(u);
deg[u]++;
deg[v]++;
}
}

bool seen[MAX_N];
int layer[MAX_N];

void init()
{
for(int u = 0; u < n; u++) {
seen[u] = false;
layer[u] = -1;
}
}

void bfs(int s)
{
vector<int> current_layer;
vector<int> next_layer;

current_layer.push_back(s);
seen[s] = true;
layer[s] = 0;

while(true) {
for(auto i=current_layer.begin(); i!=current_layer.end(); i++) {
int u = *i;
for(int d=0; d<deg[u]; d++) {
int v = adj[u][d];
if(!seen[v]) {
next_layer.push_back(v);
seen[v] = true;
layer[v] = layer[u] + 1;
}
}
}
if(next_layer.size() == 0)
break;

current_layer = next_layer;
next_layer.clear();
}
}

int main()
{
read_input();
//
}

</syntaxhighlight>

@@ แถว 72: / แถว 72: @@
+{
    read_input();
    // ....
+}
@@ แถว 143: / แถว 144: @@
+{
    read_input();
    bfs(0);
    for(int u=0; u<n; u++) {

@@ แถว 133: / แถว 133: @@
        int v = adj[u][d];
        if(!seen[v]) {
-	Q.push_back(v);
+        Q.push_back(v);
-	seen[v] = true;
+        seen[v] = true;
-	layer[v] = layer[u] + 1;
+        layer[v] = layer[u] + 1;
+       }
+     }

@@ แถว 73: / แถว 73: @@
    read_input();
    // ....
+}
 </syntaxhighlight>