欧拉回路
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=1e5+5,M=4e5+5; 4 int t,n,m,tot,in[N],ou[N],ans[M]; 5 int cnt,fro[N],to[M],nxt[M]; 6 bool vis[M]; 7 void add(int x,int y) { 8 to[++cnt]=y,nxt[cnt]=fro[x]; fro[x]=cnt; 9 in[y]++,ou[x]++; 10 } 11 12 void DFS(int x) { 13 for(int &i=fro[x];i;i=nxt[i]) { 14 int h=i; 15 if(t==1) { 16 int k=(i+1)>>1; 17 if(!vis[k]) { 18 vis[k]=1; DFS(to[i]); 19 if(h&1) ans[++tot]=k; else ans[++tot]=-k; 20 } 21 } 22 else if(!vis[i]) { 23 vis[i]=1; DFS(to[i]); 24 ans[++tot]=h; 25 } 26 } 27 } 28 29 int main() { 30 t=read(); 31 n=read(),m=read(); 32 for(int i=1;i<=m;i++) { 33 int u=read(),v=read(); 34 add(u,v); if(t==1) add(v,u); 35 } 36 if(t==1) for(int i=1;i<=n;i++) if(in[i]&1) return printf("NO"),0; 37 if(t==2) for(int i=1;i<=n;i++) if(in[i]^ou[i]) return printf("NO"),0; 38 DFS(to[1]); 39 if(tot<m) return printf("NO"),0; 40 printf("YES "); 41 for(int i=tot;i;i--) printf("%d ",ans[i]); 42 }
单词游戏
1 #include<bits/stdc++.h> 2 using namespace std; 3 int T,n,Father,in[30],out[30],fa[30]; 4 bool flag,s,t; 5 char a[1005]; 6 7 int num(char c) {return c-'a'+1;} 8 int getfa(int x) {return fa[x]==x?x:fa[x]=getfa(fa[x]);} 9 void ready() { 10 flag=s=t=false; Father=0; 11 for(int i=1;i<=26;i++) fa[i]=i; 12 memset(in,0,sizeof(in)); 13 memset(out,0,sizeof(out)); 14 } 15 16 int main() { 17 scanf("%d",&T); 18 while(T--) { 19 ready(); 20 scanf("%d",&n); 21 for(int i=1;i<=n;i++) { 22 scanf("%s",a+1); 23 int len=strlen(a+1); 24 out[num(a[1])]++,in[num(a[len])]++; 25 fa[getfa(num(a[1]))]=getfa(num(a[len])); 26 } 27 for(int i=1;i<=26;i++) { 28 if(in[i]==out[i]) continue; 29 else if(in[i]+1==out[i]&&!s) s=true; 30 else if(in[i]==out[i]+1&&!t) t=true; 31 else {flag=true; break;} 32 } 33 for(int i=1;i<=26;i++) 34 if(in[i]||out[i]) { 35 if(!Father) Father=getfa(i); 36 else if(Father^getfa(i)) {flag=true; break;} 37 } 38 if(flag) printf("The door cannot be opened. "); 39 else printf("Ordering is possible. "); 40 } 41 }
Ant Trip
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=1e5+5; 4 int n,m,ans,d[N],fa[N],s[N]; 5 bool vis[N]; 6 vector<int> v; 7 8 int getfa(int x) {return fa[x]==x?x:fa[x]=getfa(fa[x]);} 9 void ready() { 10 ans=0; 11 v.clear(); 12 memset(d,0,sizeof(d)); 13 memset(vis,0,sizeof(vis)); 14 memset(s,0,sizeof(s)); 15 for(int i=1;i<=n;i++) fa[i]=i; 16 } 17 18 int main() { 19 while(~scanf("%d%d",&n,&m)) { 20 ready(); 21 for(int i=1;i<=m;i++) { 22 int a=read(),b=read(); 23 d[a]++,d[b]++; 24 fa[getfa(a)]=getfa(b); 25 } 26 for(int i=1;i<=n;i++) { 27 int x=getfa(i); 28 if(!vis[x]) { 29 v.push_back(x); 30 vis[x]=1; 31 } 32 if(d[i]&1) s[x]++; 33 } 34 for(int i=0;i<v.size();i++) { 35 int x=v[i]; 36 if(d[x]==0) continue; 37 if(s[x]==0) ans++; 38 else ans+=s[x]/2; 39 } 40 printf("%d ",ans); 41 } 42 }