#include using namespace std; const int N = 1e5 + 10, M = N << 1; /* 7e5+10 =700000*4/1024/1024=2.67MB 这内存也不大啊,为啥会SE呢?不是说64MB的上限吗? 被卡的好难受,这是逼我去用并查集+公式解题啊! */ //邻接表 int e[M], h[N], idx, ne[M]; void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; } bool st[N]; //标识某个节点号是不是使用过 bool vis[N]; //是不是在dfs过程中搜索过 int flag; // true:满足两个条件 false:不满足两个条件 (1)是不是有环,要求无环 (2)是不是连通,要求连通 // dfs无向图判环 void dfs(int u, int fa) { //从u节点开始搜索,它的父节点是fa,输入fa的意义在于不能走回头路,防止死循环 vis[u] = true; //标识u已经搜索过了 for (int i = h[u]; ~i; i = ne[i]) { //枚举u的每一条出边 int j = e[i]; if (j == fa) continue; //放过来源节点 if (vis[j]) { //如果j被搜索过,说明有环 flag = false; //标识有环 return; } dfs(j, u); //继续搜索j节点,它的父节点是u } } //每组输入的清空与初始化 void init() { memset(st, 0, sizeof(st)); memset(vis, 0, sizeof(vis)); memset(h, -1, sizeof h); idx = 0; } int main() { int a, b; init(); while (scanf("%d%d", &a, &b) && ~a && ~b) { if (a && b) { //如果输入的a,b是两个非零数字 st[a] = st[b] = true; //标识a,b已使用 add(a, b), add(b, a); //添加两条无向边 } else { //如果输入的是两个0,描述是一组数据输入结束 flag = true; //默认是无环+连通图 // 1、检查是不是无环 for (int i = 1; i < N; i++) //枚举每个节点 if (st[i]) { //如果i节点使用过 //从找到的第一个使用过的节点开始进行dfs扫描 dfs(i, i); break; } // 2、检查连通性 if (flag) { //扫描完的结果:1、找到了环,2、没有找到环 //下面将现次枚举每个使用过的点,查看它是不是在dfs过程中被扫描到了,如果存在使过未扫到的点,则说明不连通 for (int i = 1; i < N; i++) if (st[i] && !vis[i]) { //如果存在出现过,但dfs没有扫描到的点,说明不连通 flag = false; break; } } flag ? puts("Yes") : puts("No"); //两个条件都满足,输出Yes,否则输出No init(); //因为要输入下一组数据,需要清空状态数组 } } return 0; }