sonprao

graph1

Dec 26th, 2018
89
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define FOR(i,a,b) for(i=a;i<=b;i++)
  3. #define mp(i,j) make_pair(i,j)
  4. using namespace std;
  5. pair <int,int> a[100005];
  6. map< pair<int,int>,int > kt;
  7. int n,m,q,i,h,k,c,j,d,u,t;
  8. int gr[100005], dem[100005];
  9. bool cmp_pair(pair<int, int> A, pair<int, int> B) {
  10. return (A.first < B.first || (A.first == B.first && A.second < B.second));
  11. }
  12. int main()
  13. {
  14. c=0;
  15. cin>>n>>m>>q;
  16. FOR(i,1,m)
  17. {
  18. cin>>h>>k;
  19. if (h<k)
  20. {
  21. a[i].first=h;
  22. a[i].second=k;
  23. kt[make_pair(h,k)]=1;
  24. kt[make_pair(k,h)]=1;
  25. }
  26. else
  27. {
  28. a[i].first=k;
  29. a[i].second=h;
  30. kt[make_pair(h,k)]=1;
  31. kt[make_pair(k,h)]=1;
  32. }}
  33. sort(a+1,a+1+m,cmp_pair);
  34. FOR(i,1,n) gr[i]=i;
  35. FOR(i,1,n) dem[i]=1;
  36. FOR(i,1,m)
  37. {
  38. if (gr[a[i].first]==gr[a[i].second]) continue;
  39. if (gr[a[i].first]<gr[a[i].second])
  40. {gr[a[i].second]=gr[a[i].first];
  41. dem[gr[a[i].first]]++;}
  42. else
  43. {gr[a[i].first]=gr[a[i].second];
  44. dem[gr[a[i].second]]++;}
  45. }
  46. FOR(i,1,n) if (dem[i]>1) { c++; d+=dem[i];}
  47. cout<<c<<endl;
  48. FOR(i,1,q)
  49. {
  50. cin>>t>>u;
  51. if (kt.find(make_pair(t,u))!=kt.end()) cout<<"2"<<endl;
  52. else if (gr[t]==gr[u]) cout<<"1"<<endl;
  53. else cout<<"0"<<endl;
  54. }
  55. //FOR(i,1,n) cout<<i<<" la "<<dem[i]<<endl;
  56. //FOR(i,1,m) cout<<a[i].first<<" "<<a[i].second;=<<endl;
  57. return 0;
  58. }
RAW Paste Data