Guest User

Untitled

a guest
Apr 25th, 2018
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.42 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <cmath>
  5. #include <cstdio>
  6. #include <algorithm>
  7. #include <set>
  8.  
  9. using namespace std;
  10. vector< vector<int> > nat;//relation
  11. int lastnatindex = 0;
  12. vector<int> p;//people nat index;
  13. vector<int> s;//number of places
  14.  
  15. int main()
  16. {
  17. //freopen("wedding.in","r",stdin);
  18. //freopen("wedding.out","w",stdout);
  19. freopen("iput.txt","r",stdin);
  20. freopen("outp.txt","w",stdout);
  21. int n,m,k;
  22. cin>>n>>m>>k;
  23. p.resize(n+1);
  24.  
  25. for(int i = 1; i<=n;i++)
  26.     p[i] = -1;
  27. int t1,t2;
  28. for(int i = 0;i<m;i++)
  29. {
  30.     cin>>t1>>t2;
  31.     if(p[t1]!=-1)
  32.     {
  33.         nat[p[t1]].push_back(t2);
  34.         p[t2]=p[t1];
  35.     }
  36.     else if(p[t2]!=-1)
  37.     {
  38.         nat[p[t2]].push_back(t1);
  39.         p[t1]=p[t2];
  40.     }
  41.     else
  42.     {
  43.         nat.resize(lastnatindex+1);
  44.         p[t2]=nat.size()-1;
  45.         p[t1]=p[t2];
  46.         nat[lastnatindex].push_back(t1);
  47.         nat[lastnatindex].push_back(t2);
  48.         lastnatindex++;
  49.     }
  50. }
  51.  
  52. s.resize(k);
  53. for(int i =0;i<k;i++)
  54.     cin>>s[i];
  55.  
  56. int count = 0 ;
  57.  
  58.  
  59. vector<int> ss(n+1);
  60. for(int i =0;i<nat.size();i++)
  61.     ss[nat[i].size()]=1;
  62.  
  63. for(int i =0;i<s.size();i++)
  64. {
  65.     for(int j =0;j<nat.size();j++)
  66.     {
  67.         if(nat[j].size() == s[i] && ss[nat[j].size()]==1 )
  68.         {
  69.             ss[nat[j].size()]=0;
  70.             count++;
  71.             break;
  72.         }
  73.     }
  74. }
  75.  
  76. bool t = false;
  77. for(int i =0;i<ss.size();i++)
  78. if(ss[i]!=0){t = true;break;}
  79. if(t == false)
  80. {
  81. for(int i =1;i<p.size();i++)
  82.     if(p[i]==-1){t = true;break;}
  83. }
  84. if(t)count++;
  85. cout<<count;
  86. return 0;
  87. }
Add Comment
Please, Sign In to add comment