ABC287C验证图是否一条链

#include <stdio.h>
#define N 200005
int n, m, i, j, k, a, b, c, f[N], r[N];
int find(int x){
    if(x == f[x]) return x;
    return f[x] = find(f[x]);
}
int main(){
    scanf("%d%d", &n, &m);
    for(i=1; i<=n; i++) f[i] = i;
    for(i=1; i<=m; i++){
        scanf("%d%d", &a, &b);
        f[find(a)] = find(b);
        r[a]++, r[b]++;
    }//n-1条边的连通图是棵树
    for(i=1; i<=n; i++){
        if(find(i) != find(1)) m = 0;
        if(r[i] == 1) c++;
        else if(r[i] != 2) m = 0;
    }//只有两个度为1的点就是一条链
    if(m==n-1 && c==2) printf("Yes\n");
    else printf("No\n");
    return 0;
}

深搜暴力做法：

#include <stdio.h>
#define N 200005
int n, m, u, i, j, k, a, b, c[N], v[N], t[N][5];
void cun(int a, int b){
    if(++c[a] > 2) u = -1e9;//至多2条边 
    else t[a][c[a]] = b;
}
void dfs(int a){
    int b, i;
    if(v[a]) return;
    v[a] = 1, u++;//能到多少个点
    for(i=1; i<=c[a]; i++){
        dfs(t[a][i]);
    }
}
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);//一棵树，边数不超过2即可 
    if(u==n && m==n-1) printf("Yes\n");
    else printf("No\n");
    return 0;
}