Algo lab/read graph and bfs

จาก Theory Wiki
รุ่นแก้ไขเมื่อ 03:41, 5 พฤศจิกายน 2563 โดย Jittat (คุย | มีส่วนร่วม) (สร้างหน้าด้วย "== First version == <syntaxhighlight lang="cpp"> #include <iostream> #include <vector> using namespace std; const int MAX_N = 100010; int m,n; vector<...")
(ต่าง) ←รุ่นแก้ไขก่อนหน้า | รุ่นแก้ไขล่าสุด (ต่าง) | รุ่นแก้ไขถัดไป→ (ต่าง)
ไปยังการนำทาง ไปยังการค้นหา

First version

#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();
  //
}