SHARE
TWEET

Untitled

a guest Dec 18th, 2018 45 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <fstream>
  2. #include <iostream>
  3. #include <vector>
  4. #include <algorithm>
  5. #define Mod 666013
  6. #define Nmax 100002
  7. using namespace std;
  8. ifstream fin ("gasti.in");
  9. ofstream fout ("gasti.out");
  10. vector<int>a[Nmax];
  11. int n,nr,contor,max1=-1,max2=-1,aux1,rez,D;
  12. bool viz[Nmax];
  13. int cate[Nmax];
  14. void dfs(int k,int contor)
  15. {
  16.     viz[k]=1;
  17.     nr++;
  18.     vector<int>::iterator it;
  19.     for (it=a[k].begin(); it!=a[k].end(); it++)
  20.     {
  21.         if (viz[ *it ]==0)
  22.             dfs( *it,contor);
  23.     }
  24. }
  25. int main()
  26. {
  27.     int m,c,b,i,j,ok;
  28.     fin>>n>>m;
  29.     for (i=1; i<=m; i++)
  30.     {
  31.         fin>>b>>c;
  32.        a[b].push_back(c);
  33.        a[c].push_back(b);
  34.     }
  35.     for (i=1; i<=n; i++)
  36.     {
  37.         if (viz[i]==0)
  38.         {
  39.             contor++;
  40.             nr=0;
  41.             dfs(i,contor);
  42.             cate[nr]++;
  43.             if (nr>max1)
  44.             {
  45.                 max2=max1;
  46.                 max1=nr;
  47.             }
  48.             else
  49.             {
  50.                 if (nr>max2)
  51.                     max2=nr;
  52.             }
  53.         }
  54.     }
  55.     long long x,y,calcul;
  56.     if (max1!=max2)
  57.     {
  58.         x=(1LL*cate[max1]*max1) %Mod;
  59.         y=(1LL*cate[max2]*max2) %Mod;
  60.     }
  61.     else
  62.     {
  63.         x=(1LL*max1*max1) %Mod;
  64.         y=(1LL*cate[max1]*(cate[max1]-2)/2)%Mod;
  65.     }
  66.     calcul=(1LL*x*y) %Mod;
  67.     fout<<contor<<" "<<calcul<<"\n";
  68.     fin.close();
  69.     fout.close();
  70.     return 0;
  71. }
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