cdoj 韩爷的情书有向图欧拉路径-白红宇

cdoj 韩爷的情书有向图欧拉路径

阅读量：4935 次

发布时间：2019-06-11

本文共 1847 字，大约阅读时间需要 6 分钟。

//欧拉回路

解法：首先判断欧拉回路存在性：1、连通 2、没有出度入度相差大于1的点 3、如果有出度入度相差等于1的点那么必须有两个，一个出度大于入度作为起点，一个入度大于出度作为终点。

在确定了起点后，用dfs法找欧拉回路。

关于dfs找欧拉回路：其实就是欧拉回路存在的充要性定理的证明，先走到底（最后走到的一定是终点，如果重点起点固定的话），然后再递归回来找圈，因为图连通，后来找到的圈也可以加到里面。

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 #include
           
             8 #include
            
              9 #include
              10 #include
              
                11 #include
               
                 12 13 using namespace std; 14 15 int e[5000][5000]; 16 int n; 17 int din[5000],dout[5000]; 18 char s[5]; 19 int maxLen; 20 int start; 21 int num=0; 22 char ans[200007]; 23 bool flag=false; 24 25 int getid(char c){ 26 if (c<='z' && c>='a') return c-'a'; 27 if (c<='Z' && c>='A') return c-'A'+26; 28 return c-'0'+52; 29 } 30 31 int getidfrom(char* s){ 32 return getid(s[0])*62+getid(s[1]); 33 } 34 35 int getidto(char* s){ 36 return getid(s[1])*62+getid(s[2]); 37 } 38 39 char getch(int x){ 40 if (x<26 && x>=0) return 'a'+x; 41 if (x<52 && x>=26) return 'A'+x-26; 42 return x+'0'-52; 43 } 44 45 void dfs(int now){ 46 for (int i=0;i<=maxLen;i++){ 47 if (e[now][i]>0){ 48 e[now][i]--; 49 dfs(i); 50 } 51 } 52 if (!flag){ 53 flag=true; 54 ans[num++]=getch(now%62); 55 } 56 ans[num++]=getch(now/62); 57 } 58 59 int main(){ 60 scanf("%d",&n); 61 memset(e,0,sizeof(e)); 62 memset(din,0,sizeof(din)); 63 memset(dout,0,sizeof(dout)); 64 maxLen=getid('9')*62+getid('9'); 65 for (int i=0;i
                
                 1){ 79 printf("NO\n"); 80 return 0; 81 } 82 if (din[i]>dout[i]) cnt1++; 83 if (din[i]
                 
                  =0;i--){ 99 printf("%c",ans[i]);100 }101 printf("\n");102 return 0;103 }104 /*105 4106 baa107 caa108 aax109 aay110 111 10112 Aa3113 a3X114 3XX115 XXy116 Xy1117 y12118 123119 234120 345121 456122 123 5124 123125 234126 345127 456128 567129 130 3131 123132 231133 312134 */

转载于:https://www.cnblogs.com/baby-mouse/p/4529457.html

你可能感兴趣的文章