ABC284E爆搜路径稀疏矩阵邻接表

#include <stdio.h>
const int N=200050, M=1e6;
int n, m, i, j, k, a, b, c, h[N], v[N];
struct AB{
    int a, b, n;
} d[N*2];
void cun(int a, int b){
    d[++k].a = a, d[k].b = b;
    d[k].n = h[a], h[a] = k;
}
void dfs(int a){
    int b, i;
    if(++c >= M) return;
    v[a] = 1;
    for(i=h[a]; i; i=d[i].n){
        b = d[i].b;
        if(!v[b]) dfs(b);
    }
    v[a] = 0;
}//爆搜所有路径，因为限定M次，所以不超时 
int main(){
    scanf("%d%d", &n, &m);
    for(i=1; i<=m; i++){
        scanf("%d%d", &a, &b);
        cun(a, b);
        cun(b, a);
    }
    dfs(1);
    printf("%d\n", c>M?M:c);
    return 0;
}

因为每个点不超过10条边，所以可以开二维数组存储。

#include <bits/stdc++.h>
const int N=200005, M=1e6;
using namespace std;
int n, m, i, j, k, a, b, ans;
int s[N][15], c[N], v[N];
void dfs(int a){
    if(v[a]) return;
    if(ans >= M) return;
    v[a] = 1, ans++;
    for(int i=1; i<=c[a]; i++){
        dfs(s[a][i]);
    }//循环次数不超过10 
    v[a] = 0;
}
int main(){
    scanf("%d%d", &n, &m);
    for(i=1; i<=m; i++){
        scanf("%d%d", &a, &b);
        s[a][++c[a]] = b;
        s[b][++c[b]] = a;
    }//每个点至多10条边 
    dfs(1);
    printf("%d\n", ans>M?M:ans);
    return 0;
}