欧拉回路

1 #include
     
       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
     

 

单词游戏

1 #include
     
       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.\n");39         else printf("Ordering is possible.\n");40     }41 }
     

 

Ant Trip

1 #include
     
       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
      
        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