邻接表示例程序

输入：n，m代表顶点数目和边数。然后m行，代表每个边的起点和终点。0 0 表示结束。 输出：第一行为n个正整数，表示每个点的出度；第二行为n个正整数，表示每个点的入度。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x3f3f3f3f;
const int  MIN =  -0x3f3f3f3f;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};
const int MAX = 100;
struct ArcNode{  // 边节点
  int adjvex; ArcNode *nextarc;
};
struct VNode{  // 顶点
  int data;
  ArcNode *head1; // 出边表表头指针
  ArcNode *head2;  // 入边表表头指针
};
struct LGraph{ // 临界表结构体
  VNode vertexs[MAX];  // 顶点数组
  int vexnum, arcnum;
};
LGraph lg;
void CreateLG()
{
  int i = 0; ArcNode *pi; int v1, v2;
  //scanf("%d%d", &lg.vexnum, &lg.arcnum);
  for (i = 0; i < lg.vexnum; ++i) lg.vertexs[i].head1 = lg.vertexs[i].head2 = NULL;
  for (i = 0; i < lg.arcnum; ++i){
    scanf("%d%d", &v1, &v2); v1--; v2--;
    pi = new ArcNode; pi->adjvex = v2; pi->nextarc = lg.vertexs[v1].head1;
    lg.vertexs[v1].head1 = pi;
    pi = new ArcNode; pi->adjvex = v1; pi->nextarc = lg.vertexs[v2].head2;
    lg.vertexs[v2].head2 = pi;
  }
}
void DeleteLG()
{
  ArcNode *pi; int i;
  for (i = 0; i < lg.vexnum; ++i){
    pi = lg.vertexs[i].head1;
    while (pi){
      lg.vertexs[i].head1 = pi->nextarc;
      delete pi;
      pi = lg.vertexs[i].head1;
    }
    pi = lg.vertexs[i].head2;
    while (pi){
      lg.vertexs[i].head2 = pi->nextarc;
      delete pi;
      pi = lg.vertexs[i].head2;
    }
  }
}

int main(void){
#ifndef ONLINE_JUDGE
  freopen("neighlist.in", "r", stdin);
#endif
  int i, id, od; ArcNode *pi;
  while (1){
    int n, m; scanf("%d%d", &n, &m);
    if (n+m == 0) break;
    lg.vexnum = n; lg.arcnum = m; CreateLG();
    for (i = 0; i < lg.vexnum; ++i){
      od = 0;
      pi = lg.vertexs[i].head1;
      while (pi){
        od++; pi = pi->nextarc;
      }
      if (i == 0) printf("%d", od);
      else printf(" %d", od);
    }
    printf("\n");
    for (i = 0; i < lg.vexnum; ++i){
      id = 0; pi = lg.vertexs[i].head2;
      while (pi){
        id++; pi = pi->nextarc;
      }
      if (i == 0) printf("%d", id);
      else printf(" %d", id);
    }
    printf("\n");
  }

  return 0;
}

　　也不觉得难写了……