1726: 链式前向星

#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<bool> vis;//标记
vector<int> head, nxt, to;//头，下一个结点下标，to记录边到达的结点

// C++ Version
// head[u] 和 cnt 的初始值都为 -1
void add(int u, int v) {//头插法
  nxt.push_back(head[u]);// 当前边的后继
  head[u] = to.size();// 起点 u 的第一条边
  to.push_back(v);// // 当前边的终点
}

bool find_edge(int u, int v) {
  for (int i = head[u]; ~i; i = nxt[i]) {  // ~i 表示 i != -1
    if (to[i] == v) {
      return true;
    }
  }
  return false;
}

void dfs(int u) {
  if (vis[u]) return;
  vis[u] = true;
  cout<<u<<" ";
  for (int i = head[u]; ~i; i = nxt[i]) dfs(to[i]);
}

int main() {
  cin >> n >> m;

  vis.resize(n + 1, false);//初始化为0 
  head.resize(n + 1, -1);//初始化为-1 

  for (int i = 1; i <= m; ++i) {
    int u, v;
    cin >> u >> v;
    add(u, v);
    add(v,u) ; 
  }
  dfs(1);

  return 0;
}