题意:有一颗n个点的树,然后有两行列数无限的点,问这颗树能否画出。能画出输出Yes,否则输出No
在纸上画一画可以知道,首先对于一个点,它衍生出来的最左边的那个点和最右边的那个点可以衍生出>2个点,这个点除了左边和右边以外的那两个点,只能衍生出2个点,然而这些点又只能衍生出一个点。所以对于每个连接数>2的点来说,它最多只能有2个点连接数>=3
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <set> #include <vector> #include <map> #include <queue> #include <set> #include <algorithm> #include <limits> using namespace std; typedef long long LL; const int MAXN=1e+5 + 1000; const int INF = numeric_limits<int>::max(); const LL LL_INF= numeric_limits<LL>::max(); struct Edge { int to,next; Edge(){} Edge(int _to,int _next):to(_to),next(_next){} }e[MAXN<<2]; int head[MAXN],tot; void init(){ memset(head,-1,sizeof(head)); tot=0; } void AddEdge(int u,int v){ e[tot]=Edge(v,head[u]); head[u]=tot++; e[tot]=Edge(u,head[v]); head[v]=tot++; } int du[MAXN],vis[MAXN],res[MAXN]; void dfs(int u){ vis[u]=1; for(int i=head[u];~i;i=e[i].next){ if(du[e[i].to]<=2&&!vis[e[i].to])dfs(e[i].to); } } int main() { int n; while(~scanf("%d",&n)){ init(); memset(du,0,sizeof(du)); memset(vis,0,sizeof(vis)); memset(res,0,sizeof(res)); for(int i=0,x,y;i<n-1;i++){ scanf("%d%d",&x,&y); AddEdge(x,y); ++du[x];++du[y]; } for(int i=1;i<=n;i++)if(du[i]==1)dfs(i); int flag=0; for(int u=1;u<=n;u++){ if(!vis[u]){ for(int i=head[u];~i;i=e[i].next){ int v=e[i].to; if(vis[v])res[u]=min(res[u]+1,2); } } } for(int u=1;u<=n;u++){ if(!vis[u]){ int cnt=0; for(int i=head[u];~i;i=e[i].next){ int v=e[i].to; if(!vis[v]&&du[v]-res[v]>1)++cnt; } if(cnt>2){ flag=1;break; } } } if(flag)puts("No"); else puts("Yes"); } return 0; }
|