SHARE
TWEET

conexidad

TurcuCiprian Jan 22nd, 2020 69 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3. using namespace std;
  4. ifstream fin("conexidad.in");
  5. ofstream fout("conexidad.out");
  6. int m,n,x,a[102][102],viz[102],z,j,i,c,b,maxextra,compcon,gata,extra[102],k;
  7. void dfs(int k)
  8. {
  9.     int j;
  10.     viz[k]=compcon;
  11.     for(j=1; j<=n; j++)
  12.     {
  13.         if(a[k][j]==1 && viz[j]==0)
  14.             dfs(j);
  15.     }
  16. }
  17. int main()
  18. {
  19.     fin>>n>>m;
  20.     for(i=1; i<=m; i++)
  21.     {
  22.         fin>>b>>c;
  23.         a[b][c]=a[c][b]=1;
  24.     }
  25.     gata=0;
  26.     compcon=0;
  27.     while(gata==0)
  28.     {
  29.         i=1;
  30.         while(i<=n && viz[i]!=0)
  31.             i++;
  32.         if(i<=n)
  33.         {
  34.             z=i;
  35.             compcon++;
  36.             dfs(z);
  37.         }
  38.         else
  39.             gata=1;
  40.     }
  41.     i=1;
  42.     /*for(i=1;i<=n;i++)
  43.     {
  44.         fout<<viz[i]<<" ";
  45.     }
  46.     fout<<endl;
  47.     */
  48.     i=1;
  49.     while(i<n)
  50.     {
  51.             if(viz[i]!=viz[i+1])
  52.             {
  53.                 extra[i+1]++;
  54.                 i=i+2;
  55.                 k++;
  56.             }
  57.             else i++;
  58.     }
  59.     /*for(i=1; i<=n; i++)
  60.         fout<<viz[i]<<" ";
  61.     fout<<endl;
  62.     for(i=1; i<=n; i++)
  63.         fout<<extra[i]<<" ";
  64.     fout<<endl;
  65.     */
  66.     for(i=1; i<=n; i++)
  67.         if(extra[i]>maxextra)
  68.             maxextra=extra[i];
  69.     fout<<maxextra<<endl;
  70.     fout<<k<<endl;
  71.     i=1;
  72.      /*for(int i=1;i<=n;i++)
  73.     {
  74.         fout<<viz[i]<<" ";
  75.     }
  76.     fout<<endl;
  77.     */
  78.     while(k>0)
  79.     {
  80.  
  81.  
  82.         if(viz[i]!=viz[i+1])
  83.         {
  84.             fout<<i<<" "<<i+1<<endl;
  85.             i=i+2;
  86.             k--;
  87.         }
  88.         else
  89.             i++;
  90.     }
  91.     return 0;
  92. }
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