• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# graph1

sonprao Dec 26th, 2018 76 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top