﻿

# 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