1.用邻接表求顶点k的入度

#include <iostream>
#include <vector>

using namespace std;

const int N = 510;

int n, m, k;
vector<Node*> head(N, nullptr);

struct Node
{
    int id; // 编号
    Node* next;
    Node(int _id) : id(_id), next(nullptr) {}
};

void add(int a, int b)
{
    Node* p = new Node(b);
    p->next = head[a];
    head[a] = p;
}

// 计算顶点k的入度
int in_degree(int k)
{
    int count = 0;
    for(int i = 1; i <= n; i++)
    {
        for(auto p = head[i]; p; p = p->next)
        {
            if(p->id == k) count++;
        }
    }
    return count;
}

int main()
{
    cin >> n >> m >> k;
    while (m--)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }

    int k_in_degree = in_degree(k);

    return 0;
}

2.dfs非递归实现

#include <iostream>
#include <cstring>
#include <stack>

using namespace std;

const int N = 510;  // 定义最大节点数量

int n, m;           // n 表示节点数，m 表示边数
bool st[N];         // 用于记录节点是否被访问过

// 定义链表节点结构体，用于存储图的邻接表
struct Node
{
    int id;         // 节点的标识符
    Node* next;     // 指向下一个邻接点的指针
    Node(int _id) : id(_id), next(NULL) {}  // 构造函数，初始化节点标识符和指针
}* head[N];         // 邻接表头指针数组

// 添加一条从 a 到 b 的有向边
void add(int a, int b)
{
    Node* p = new Node(b);  // 创建新节点 p，存储节点 b
    p->next = head[a];      // 将新节点 p 插入到链表头部
    head[a] = p;            // 更新链表头指针为 p
}

// 深度优先搜索（非递归实现）
void dfs(int u)
{
    stack<int>s;
    s.push(u);
    while(s.size())
    {
        int t=s.top();
        s.pop();
        if(st[t])continue;
        cout<<t<<" ";
        st[t]=true;
        for(auto p=head[t];p;p=p->next)
        {
            int j=p->id;
            if(!st[j])
            {
                s.push(j);
            }
        }
    }
}

int main()
{
    cin >> n >> m;  // 输入节点数和边数
    while (m -- )   // 读取每条边
    {
        int a, b;
        cin >> a >> b;
        add(a, b);  // 添加有向边 a -> b
    }

    // 输出图的邻接表表示
    for (int i = 1; i <= n; i ++)
    {
        printf("%d: ", i);
        for (Node* p = head[i]; p; p = p->next)
            printf("%d -> ", p->id);
        puts("NULL");
    }

    puts("-------------------");

    // 对每个节点进行 DFS，如果该节点未被访问过
    for (int i = 1; i <= n; i ++)
        if (!st[i])
            dfs(i);

    return 0;
}