// 小希的迷宫.cpp : 定义控制台应用程序的入口点。#include "stdafx.h"#include <iostream>#include <stdio.h>using namespace std;struct Edge//用结构体存储边信息，flag表示该边是否被选取。{ int v1,v2; int flag;}edge[500];int v[100001];int visited;bool dfs(Edge *edge,int v,int size){ for(int i=0;i<size;i++) { if(visited>=size) return 0; if(edge[i].v1==v && edge[i].flag==0) { edge[i].flag=1; visited++; dfs(edge,edge[i].v2,size); } if(edge[i].v2==v && edge[i].flag==0) { edge[i].flag=1; visited++; dfs(edge,edge[i].v1,size); } } return 0;}int main(){ int m,n; while(cin>>m>>n) { if(m==-1 && n==-1) return 0; if(m==0 && n==0)//判断特殊情况：开始就输入两个0 cout<<"Yes\n"; else { int loop=0; int size_v=0,size_e=0,symbol=0,max_v;//max_v用来存储点的最大编号 visited=0; memset(v,0,sizeof(v)); max_v=(m>=n)?m:n; for(int i=0;i<500;i++)//初始化结构体 { edge[i].flag=0; } edge[0].v1=m; edge[0].v2=n; v[m]=1;v[n]=1; size_e++; while(cin>>m>>n,m!=0 || n!=0) { edge[size_e].v1=m; edge[size_e++].v2=n; v[m]=1;v[n]=1; if(m>max_v) max_v=m; if(n>max_v) max_v=n; } for(int i=1;i<=max_v;i++)//统计顶点的个数 if(v[i]==1) size_v++; dfs(edge,edge[0].v1,size_e);//深搜只是标记是否是连通图。 for(int i=0;i<size_e;i++)//判断图是否连通 { if(edge[i].flag==0)//不连通 { symbol=1; break; } } if(symbol==1) cout<<"No\n"; else { if(size_e>=size_v)//判断是否有环：某一个连通分支的边数>=该分支的顶点数，则有环。 cout<<"No\n"; else cout<<"Yes\n"; } } }}
