Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on May 5th, 2012  |  syntax: C++  |  size: 2.58 KB  |  hits: 13  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <cstring>
  4. #include <vector>
  5. #include <map>
  6.  
  7. using namespace std;
  8. long n,i,t1,t2,m,d[100000],ans,clr[100000],t,bst[1000][1000],j;
  9. map<string,long> mp;
  10. bool boo,fix[100000];
  11. vector <long> a1,a2,v[100000];
  12. string s1[100000],s2[100000],s[100000];
  13.  
  14. void go(long k)
  15. {
  16.      fix[k]=true;
  17.      clr[k]=t;
  18.      bst[t][0]++;
  19.      bst[t][bst[t][0]]=k;
  20.      long i;
  21.      for(i=0;i<v[k].size();i++)
  22.      if(!fix[v[k][i]]) go(v[k][i]);
  23.      
  24. }
  25.  
  26. void pnt(long k,long c)
  27. {
  28.      long i;
  29.      clr[k]=c;
  30.      bst[c][0]++;
  31.      bst[c][bst[c][0]]=k;
  32.      for(i=0;i<v[k].size();i++)
  33.      if(clr[v[k][i]]!=c) pnt(v[k][i],c);
  34.      
  35. }
  36.  
  37. long fndbst(long k)
  38. {
  39.      long i,ans;
  40.      ans=bst[k][1];
  41.      for(i=1;i<=bst[k][0];i++)
  42.      if(d[bst[k][i]]%2) {ans=bst[k][i];break;}
  43.      return ans;
  44. }
  45.  
  46.  
  47. main()
  48. {
  49.       freopen("voyage.in","r",stdin);
  50.       freopen("voyage.out","w",stdout);
  51.       n=1;
  52.       s[0]="BATUMI";
  53.       mp[s[0]]=1;
  54.       cin>>m;
  55.       for(i=1;i<=m;i++)
  56.       {
  57.                        cin>>s1[i]>>s2[i];
  58.                        if(!mp[s1[i]]) {s[n++]=s1[i]; mp[s1[i]]=n; }
  59.                        if(!mp[s2[i]]) {s[n++]=s2[i]; mp[s2[i]]=n; }
  60.       }
  61.      
  62.       for(i=1;i<=m;i++)
  63.       {
  64.       d[mp[s1[i]]]++;
  65.       d[mp[s2[i]]]++;
  66.       v[mp[s1[i]]].push_back(mp[s2[i]]);
  67.       v[mp[s2[i]]].push_back(mp[s1[i]]);
  68.       }
  69.      
  70.      
  71.       for(i=1;i<=n;i++)
  72.         if(!fix[i]) {t++; go(i);}
  73.        
  74.       for(i=1;i<n;i++)
  75.        for(j=i+1;j<=n;j++)
  76.        if (clr[i]!=clr[j]) {
  77.                            ans++;
  78.                            t1=fndbst(clr[i]);
  79.                            t2=fndbst(clr[j]);
  80.                            a1.push_back(t1-1);
  81.                            a2.push_back(t2-1);
  82.                            d[t1]++;
  83.                            d[t2]++;
  84.                            pnt(t2,clr[i]);
  85.                            }              
  86.      
  87.       while(1)
  88.       {
  89.               boo=false;
  90.               for(i=1;i<=n;i++)
  91.               if(d[i]%2) {boo=true;break;}
  92.               if (!boo) break;
  93.               ans++;
  94.               t1=0;
  95.               t2=0;
  96.               for(i=1;i<=n;i++)
  97.               if((d[i]%2)|(d[i]==0)) {t1=i; break;}
  98.               for(i=t1+1;i<=n;i++)
  99.               if((d[i]%2)|(d[i]==0)) {t2=i; break;}
  100.               d[t1]++;
  101.               d[t2]++;
  102.              
  103.               a1.push_back(t1-1);
  104.               a2.push_back(t2-1);
  105.       }        
  106.      
  107.       cout<<ans<<endl;
  108.       for(i=0;i<ans;i++)
  109.       cout<<s[a1[i]]<<" "<<s[a2[i]]<<endl;
  110. }
create a new version of this paste RAW Paste Data