POJ3310.md

找到首尾两个点，连接起来，然后判断其他点是否在路径的边上

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
#include<stack>
using namespace std;
void ____(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); }
const int MAXN = 111;
int n,m,vis[MAXN],depth[MAXN];
bool inpath[MAXN];
vector<int> G[MAXN];
bool dfs(int u, int f){
    depth[u] = depth[f] + 1;
    vis[u] = 1;
    for(int i = 0; i < (int)G[u].size(); i++){
        int v = G[u][i];
        if(v==f) continue;
        if(vis[v]) return false;
        if(!dfs(v,u)) return false;
    }
    return true;
}
bool search(int u, int f, const int tail){
    if(u==tail) return inpath[u] = true;
    for(int i = 0; i < (int)G[u].size(); i++){
        int v = G[u][i];
        if(v==f) continue;
        if(search(v,u,tail)) inpath[u] = true;
    }
    return inpath[u];
}
int main(){
    int kase = 0;
    while(scanf("%d",&n)!=EOF && n){
        kase++;
        scanf("%d",&m);
        for(int i = 1; i <= n; i++) G[i].clear();
        for(int i = 1; i <= m; i++){
            int u, v;
            scanf("%d %d",&u,&v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        memset(vis,0,sizeof(vis));
        if(!dfs(1,0)){
            printf("Graph %d is not a caterpillar.\n",kase);
            continue;
        }
        bool connect = true;
        for(int i = 1; i <= n; i++) if(!vis[i]){
            connect = false;
            break;
        }
        if(!connect){
            printf("Graph %d is not a caterpillar.\n",kase);
            continue;
        }
        int rt = 1;
        for(int i = 1; i <= n; i++) if(depth[i]>depth[rt]) rt = i;
        memset(vis,0,sizeof(vis));
        dfs(rt,0);
        int tl = 2;
        for(int i = 1; i <= n; i++) if(depth[i]>depth[tl]) tl = i;
        search(rt,0,tl);
        memset(vis,0,sizeof(vis));
        for(int u = 1; u <= n; u++) if(inpath[u]){
            vis[u] = true;
            for(int i = 0; i < (int)G[u].size(); i++) vis[G[u][i]] = true;
        }
        bool ok = true;
        for(int i = 1; i <= n; i++) if(!vis[i]){
            ok = false;
            break;
        }
        if(ok) printf("Graph %d is a caterpillar.\n",kase);
        else printf("Graph %d is not a caterpillar.\n",kase);
    }
    return 0;
}