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. OK, I Understand
 
Top