题解：

核心思想

对于子任务1，我们需要判断给定的连通图是否能通过操作反向收缩到 $K_4$（4个顶点的完全图）。

关键观察：

1. $K_4$ 是最小的不可再分割的图之一
2. 一个图能反向收缩到 $K_4$，当且仅当它可以通过不断合并满足特定条件的顶点对，最终得到 $K_4$
3. 对于 $K_4$，其特性是每个顶点度数至少为3（在最终状态）

C语言实现

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

#define MAXN 100010

typedef struct {
    int to, next;
} Edge;

Edge edges[MAXN * 2];
int head[MAXN], edge_cnt;
int degree[MAXN];
bool removed[MAXN];
int n, m;

void add_edge(int u, int v) {
    edges[++edge_cnt].to = v;
    edges[edge_cnt].next = head[u];
    head[u] = edge_cnt;
    degree[u]++;
}

// 检查顶点u和v是否可以合并
bool can_merge(int u, int v) {
    // u和v必须直接相连
    bool connected = false;
    for (int i = head[u]; i; i = edges[i].next) {
        if (edges[i].to == v) {
            connected = true;
            break;
        }
    }
    if (!connected) return false;
    
    // 计算u和v的邻居集（不包括彼此）
    bool neighbor_u[MAXN] = {false};
    bool neighbor_v[MAXN] = {false};
    
    for (int i = head[u]; i; i = edges[i].next) {
        int to = edges[i].to;
        if (to != v && !removed[to]) {
            neighbor_u[to] = true;
        }
    }
    
    for (int i = head[v]; i; i = edges[i].next) {
        int to = edges[i].to;
        if (to != u && !removed[to]) {
            neighbor_v[to] = true;
            // 如果v的邻居也是u的邻居，则不能合并
            if (neighbor_u[to]) {
                return false;
            }
        }
    }
    
    return true;
}

// 尝试将图收缩到K4
bool can_reduce_to_K4() {
    int remaining = n;
    
    // 不断尝试合并顶点
    while (remaining > 4) {
        bool merged = false;
        
        for (int u = 1; u <= n; u++) {
            if (removed[u]) continue;
            
            for (int i = head[u]; i; i = edges[i].next) {
                int v = edges[i].to;
                if (removed[v] || u >= v) continue;
                
                if (can_merge(u, v)) {
                    // 合并u和v：将v合并到u上
                    // 1. v的所有邻居（除了u）变成u的邻居
                    for (int j = head[v]; j; j = edges[j].next) {
                        int w = edges[j].to;
                        if (w != u && !removed[w]) {
                            // 添加边u-w（如果不存在）
                            bool exists = false;
                            for (int k = head[u]; k; k = edges[k].next) {
                                if (edges[k].to == w) {
                                    exists = true;
                                    break;
                                }
                            }
                            if (!exists) {
                                add_edge(u, w);
                                add_edge(w, u);
                            }
                        }
                    }
                    
                    // 2. 标记v为已移除
                    removed[v] = true;
                    remaining--;
                    merged = true;
                    break;
                }
            }
            if (merged) break;
        }
        
        if (!merged) {
            // 无法继续合并
            break;
        }
    }
    
    if (remaining != 4) return false;
    
    // 检查剩下的4个点是否构成完全图K4
    int vertices[4], idx = 0;
    for (int i = 1; i <= n && idx < 4; i++) {
        if (!removed[i]) {
            vertices[idx++] = i;
        }
    }
    
    // 检查这4个点是否两两相连
    for (int i = 0; i < 4; i++) {
        for (int j = i + 1; j < 4; j++) {
            bool connected = false;
            for (int k = head[vertices[i]]; k; k = edges[k].next) {
                if (edges[k].to == vertices[j]) {
                    connected = true;
                    break;
                }
            }
            if (!connected) return false;
        }
    }
    
    return true;
}

int main() {
    int S, T;
    scanf("%d %d", &S, &T);
    
    while (T--) {
        // 初始化
        memset(head, 0, sizeof(head));
        memset(degree, 0, sizeof(degree));
        memset(removed, 0, sizeof(removed));
        edge_cnt = 0;
        
        scanf("%d %d", &n, &m);
        
        for (int i = 0; i < m; i++) {
            int a, b;
            scanf("%d %d", &a, &b);
            add_edge(a, b);
            add_edge(b, a);  // 无向图
        }
        
        // 根据子任务调用不同的判断函数
        bool result = false;
        switch(S) {
            case 1:  // 烧瓶神话
                result = can_reduce_to_K4();
                break;
            // 其他子任务需要另外实现
            default:
                result = false;
                break;
        }
        
        printf("%s\n", result ? "YES" : "NO");
        
        // 跳过空行（如果有）
        if (T > 0) {
            char ch;
            do {
                ch = getchar();
            } while (ch != '\n');
        }
    }
    
    return 0;
}

算法详细解释

1. 数据结构

• 使用邻接表存储图
• removed[]数组标记已合并（删除）的顶点
• degree[]数组记录每个顶点的度数

2. 合并条件检查 can_merge(u, v)

两个顶点u和v可以合并当且仅当：

1. u和v之间有边直接相连
2. u的所有其他邻居与v的所有其他邻居没有交集
   • 这是因为在分割操作中，原顶点的邻居被分到了两个不同的集合

3. 合并操作

当u和v可以合并时：

1. 将v合并到u上
2. v的所有邻居（除了u）都成为u的邻居
3. 标记v为已删除，减少剩余顶点数

4. 终止条件

• 不断合并直到无法继续合并或剩余顶点数为4
• 最终检查这4个顶点是否构成完全图$K_4$

其他子任务的解题思路

子任务2（月亮神话 - $C_3$）

• 目标：是否能收缩到3个顶点的环
• 策略：不断合并度数为2且满足合并条件的顶点对
• 最终检查是否剩下3个顶点构成三角形环

子任务3（太阳神话 - $K_{2,2}$）

• 目标：完全二分图，两边各2个顶点
• 策略：需要识别二分图结构
• 关键：最终图中的4个顶点应分为两组，组内无边，组间全连接

子任务4（鹰爪神话 - $K_{1,3}$）

• 目标：星形图，一个中心连接3个叶子
• 策略：反复合并"叶子"顶点到中心
• 最终检查：1个中心顶点连接3个独立的叶子顶点

子任务5（狐狸神话 - $P_4$）

• 目标：4个顶点的路径
• 策略：不断合并路径中间的度数为2的顶点
• 最终检查：4个顶点形成一条链

优化建议

1. 使用更高效的邻居检查

// 可以使用哈希集或排序后的邻居列表
bool check_neighbors_disjoint(int u, int v) {
    int neighbors_u[MAXN], count_u = 0;
    int neighbors_v[MAXN], count_v = 0;
    
    // 收集邻居并排序
    // 然后使用双指针检查交集
}

2. 避免重复检查

• 记录已经检查过的顶点对
• 只在度数或邻居发生变化时重新检查

3. 使用并查集跟踪合并

int parent[MAXN];
int find(int x) {
    return parent[x] == x ? x : (parent[x] = find(parent[x]));
}
void unite(int x, int y) {
    parent[find(y)] = find(x);
}

复杂度分析

对于子任务1的实现：

• 每次合并需要O(N+M)时间检查
• 最多进行N-4次合并
• 总复杂度：O(N×(N+M))，对于N≤1000可接受

注意事项

1. 每个子任务需要不同的合并策略
2. 需要仔细处理边界情况
3. 对于大规模数据（子任务3），需要更高效的实现

这个题解提供了解决子任务1的完整框架，其他子任务需要基于类似思想但使用不同的合并条件和终止判断。由于题目复杂性，完整的5个子任务实现会非常长，但核心思想都是通过反向操作将图收缩到目标结构。