Advertisement
hopingsteam

maxConnect si maxColor

Mar 14th, 2020
466
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.31 KB | None | 0 0
  1. #include    <iostream>
  2. #include    <fstream>
  3. #include    <vector>
  4.  
  5. using namespace std;
  6.  
  7. ifstream fin("fisier.in");
  8.  
  9. int Muchii[100][100]; // drum de la i la j
  10.  
  11. int vNoduri[100], vCulori[100]; // 0 - nevizitat | 1 - vizitat
  12.  
  13. int culori[100] = {3, 2, 3, 4, 2, 2, 0};
  14.  
  15. int n, m; // n - noduri | m - muchii
  16.  
  17. int Origin[100], oo;
  18. int OriNum[100];
  19.  
  20. void resetCulori()
  21. {
  22.     for(int i = 0; i <= n; i++)
  23.         vCulori[i] = 0;
  24. }
  25.  
  26. void DFS(int Nod, int &nrCul)
  27. {
  28.     //cout << "DFS: nodul " << Nod << "\n";
  29.     vNoduri[Nod] = 1;
  30.     if(vCulori[culori[Nod]] == 0)
  31.     {
  32.         vCulori[culori[Nod]] = 1;
  33.         nrCul++;
  34.     }
  35.    
  36.     for(int i = 0; i <= n; i++)
  37.     {
  38.         if(Muchii[Nod][i] == 1 && vNoduri[i] == 0)
  39.         {
  40.             DFS(i, nrCul);
  41.         }
  42.     }
  43. }
  44.  
  45. int maxColor()
  46. {
  47.     int maxNrCul = 0;
  48.     for(int i = 0; i <= n; i++)
  49.     {
  50.         if(!vNoduri[i])
  51.         {
  52.             //cout << "Vizitez nodul " << i << "\n";
  53.             int nrCul = 0;
  54.             DFS(i, nrCul);
  55.             //cout << "nrCul: " << nrCul << "\n";
  56.             if(nrCul > maxNrCul)
  57.             {
  58.                 maxNrCul = nrCul;
  59.             }
  60.             resetCulori();
  61.         }
  62.     }
  63.     return maxNrCul;
  64. }
  65.  
  66. void resett()
  67. {
  68.     for(int i = 0; i <= n; i++)
  69.     {
  70.         vNoduri[i] = 0;
  71.         vCulori[i] = 0;
  72.     }
  73. }
  74.  
  75. int maxConnect()
  76. {
  77.     int colorMax = 0;
  78.     for(int i = 0; i <= n; i++)
  79.     {
  80.         if(!vNoduri[i])
  81.         {
  82.             int nrCul = 0;
  83.             Origin[oo++] = i;
  84.             DFS(i, nrCul);
  85.         }
  86.     }
  87.  
  88.     for(int i = 0; i < oo; i++)
  89.     {
  90.         for(int j = i + 1; j < oo; j++)
  91.         {
  92.             int n1 = Origin[i], n2 = Origin[j];
  93.             //cout << "Legam nodul: " << n1 << " cu " << n2 << "\n";
  94.  
  95.             Muchii[n1][n2] = 1; Muchii[n2][n1] = 1;
  96.             resett();
  97.             int newColor = maxColor();
  98.             if(newColor > colorMax)
  99.                 colorMax = newColor;
  100.  
  101.             Muchii[n1][n2] = 0; Muchii[n2][n1] = 0;
  102.         }
  103.     }
  104.     return colorMax;
  105. }
  106.  
  107. int main()
  108. {
  109.     fin >> n >> m;
  110.     for(int i = 0; i < m; i++)
  111.     {
  112.         int x, y;
  113.         fin >> x >> y;
  114.         Muchii[x][y] = 1;
  115.         Muchii[y][x] = 1;
  116.     }
  117.  
  118.     //cout << maxColor();
  119.     cout << maxConnect();
  120.     return 0;
  121. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement