SHARE
TWEET

bot_popa

a guest May 22nd, 2019 67 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. int m, n, a[20][20], nr, nr1, OK, nod, k, st[20], viz[20], x, i, j, s, v[20], grad;
  5. ifstream f("graf.in");
  6. void citire()
  7. {
  8.     f>>n>>m;
  9.     int x,y,i;
  10.     for(i=1;i<=m;i++)
  11.     {
  12.         f>>x>>y;
  13.         a[x][y]=a[y][x]=1;
  14.     }
  15. }
  16.  
  17. int main()
  18. {
  19.     nr=0;
  20.     citire();
  21.     OK=0;
  22.     nod=1;
  23.     while(OK==0)
  24.     {
  25.         nr++;
  26.         k=1;
  27.         st[k]=nod;
  28.         viz[nod]=nr;
  29.         while(k>0)
  30.         {
  31.             x=st[k];
  32.             for(i=1;i<=n;i++)
  33.                 if(a[x][i]==1 && viz[i]==0)
  34.             {
  35.                 k++;
  36.                 st[k]=i;
  37.                 viz[i]=nr;
  38.                 i=n+2;
  39.             }
  40.             if(i==n+1)
  41.                 k--;
  42.         }
  43.         OK=1;
  44.         for(i=1;i<=n;i++)
  45.             if(viz[i]==0)
  46.             {
  47.                 nod=i;
  48.                 OK=0;
  49.                 i=n+1;
  50.             }
  51.     }
  52.     for(i=1;i<=n;i++)
  53.     {
  54.         s=0;
  55.         for(j=1;j<=n;j++)
  56.             s=s+a[i][j];
  57.         a[i][0]=s;
  58.     }
  59.     for(i=1;i<=nr;i++)
  60.     {
  61.         nr1=0; // nr nod componenta conexa curenta
  62.         for(j=1;j<=n;j++)
  63.             if(viz[j]==i)
  64.         {
  65.             nr1++;
  66.             v[nr1]=j;
  67.         }
  68.         OK=1; //pp. ca comp. conexa este subgraf regulat
  69.         grad=a[v[1]][0];
  70.         for(k=2;k<=nr1;k++)
  71.             if(grad!=a[v[k]][0])
  72.                 OK==0;
  73.         if(OK==1)
  74.         {
  75.             for(j=1;j<=nr1;j++)
  76.                 cout<<v[j]<<" ";
  77.             j=nr+1;
  78.         }
  79.     }
  80.     return 0;
  81. }
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