rt，我比较喜欢链式前向星，但是一直过不了，改成 vector 存就能过了，求教。

1. vector 存图（$100$ pts）

#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
    int s = 0, w= 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') w = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        s = (s << 3) + (s << 1) + (ch ^ 48);
        ch = getchar();
    }
    return s * w;
}
const int N = 5e5 + 10;
int n, m;
int head[N], ne[N], to[N], id = 1;
void add(int x, int y)
{
    to[++id] = y, ne[id] = head[x], head[x] = id;
}
bool vis[N];
int stk[N], top;
vector<int> v[N];
void dfs(int u)
{
    for(int i = head[u]; i < v[u].size(); i = head[u])
    {
        int nx = v[u][i];
        head[u] = i + 1;
        // if(vis[i]) continue;
        // vis[i] = 1;
        dfs(nx);
    }
    stk[++top] = u;
}
int in[N], out[N];
int tmp[3], cm;
signed main()
{
    n = read(), m = read();
    int s = 1;
    for(int i = 1; i <= m; i++)
    {
        int x = read(), y = read();
        // add(x, y);
        v[x].push_back(y);
        in[y]++, out[x]++;
        // s = min(s, min(x, y));
    }
    for(int i = 1; i <= n; i++)
    {
        sort(v[i].begin(), v[i].end());
        // for(int j = 0; j < v[i].size(); j++) add(i, v[i][j]);
    }
    bool fl = 1;
    for(int i = 1; i <= n; i++)
    {
        if(in[i] == out[i]) continue;
        fl = 0;
        if(out[i] == in[i] + 1) tmp[1]++, s = i;
        else if(in[i] == out[i] + 1) tmp[2]++;
        else return printf("No\n"), 0;
    }
    if((!fl) && (!(tmp[1] == tmp[2] && tmp[2] == 1))) return printf("No\n"), 0;
    dfs(s);
    while(top) printf("%lld ", stk[top--]);
    return 0;
}

2. 链式前向星（$20$ pts）

#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
    int s = 0, w= 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') w = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        s = (s << 3) + (s << 1) + (ch ^ 48);
        ch = getchar();
    }
    return s * w;
}
const int N = 5e5 + 10;
int n, m;
int head[N], ne[N], to[N], id = 1;
void add(int x, int y)
{
    to[++id] = y, ne[id] = head[x], head[x] = id;
}
bool vis[N];
int stk[N], top;
void dfs(int u, int fa)
{
    for(int i = head[u]; i; i = head[u])
    {
        int v = to[i];
        head[u] = ne[i];
        // if(vis[i]) continue;
        // vis[i] = 1;
        dfs(v, u);
    }
    stk[++top] = u;
}
vector<int> v[N];
int in[N], out[N];
int tmp[3], cm;
signed main()
{
    n = read(), m = read();
    int s = 1;
    for(int i = 1; i <= m; i++)
    {
        int x = read(), y = read();
        add(x, y);
        in[y]++, out[x]++;
        // s = min(s, min(x, y));
    }
    bool fl = 1;
    for(int i = 1; i <= n; i++)
    {
        if(in[i] == out[i]) continue;
        fl = 0;
        if(out[i] == in[i] + 1) tmp[1]++, s = i;
        else if(in[i] == out[i] + 1) tmp[2]++;
        else return printf("No\n"), 0;
    }
    if((!fl) && (!(tmp[1] == tmp[2] && tmp[1] == 1))) return printf("No\n"), 0;
    dfs(s, 0);
    while(top) printf("%lld ", stk[top--]);
    return 0;
}