Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <vector>
- using namespace std;
- ifstream fin("fisier.in");
- int Muchii[100][100]; // drum de la i la j
- int vNoduri[100], vCulori[100]; // 0 - nevizitat | 1 - vizitat
- int culori[100] = {3, 2, 3, 4, 2, 2, 0};
- int n, m; // n - noduri | m - muchii
- int Origin[100], oo;
- int OriNum[100];
- void resetCulori()
- {
- for(int i = 0; i <= n; i++)
- vCulori[i] = 0;
- }
- void DFS(int Nod, int &nrCul)
- {
- //cout << "DFS: nodul " << Nod << "\n";
- vNoduri[Nod] = 1;
- if(vCulori[culori[Nod]] == 0)
- {
- vCulori[culori[Nod]] = 1;
- nrCul++;
- }
- for(int i = 0; i <= n; i++)
- {
- if(Muchii[Nod][i] == 1 && vNoduri[i] == 0)
- {
- DFS(i, nrCul);
- }
- }
- }
- int maxColor()
- {
- int maxNrCul = 0;
- for(int i = 0; i <= n; i++)
- {
- if(!vNoduri[i])
- {
- //cout << "Vizitez nodul " << i << "\n";
- int nrCul = 0;
- DFS(i, nrCul);
- //cout << "nrCul: " << nrCul << "\n";
- if(nrCul > maxNrCul)
- {
- maxNrCul = nrCul;
- }
- resetCulori();
- }
- }
- return maxNrCul;
- }
- void resett()
- {
- for(int i = 0; i <= n; i++)
- {
- vNoduri[i] = 0;
- vCulori[i] = 0;
- }
- }
- int maxConnect()
- {
- int colorMax = 0;
- for(int i = 0; i <= n; i++)
- {
- if(!vNoduri[i])
- {
- int nrCul = 0;
- Origin[oo++] = i;
- DFS(i, nrCul);
- }
- }
- for(int i = 0; i < oo; i++)
- {
- for(int j = i + 1; j < oo; j++)
- {
- int n1 = Origin[i], n2 = Origin[j];
- //cout << "Legam nodul: " << n1 << " cu " << n2 << "\n";
- Muchii[n1][n2] = 1; Muchii[n2][n1] = 1;
- resett();
- int newColor = maxColor();
- if(newColor > colorMax)
- colorMax = newColor;
- Muchii[n1][n2] = 0; Muchii[n2][n1] = 0;
- }
- }
- return colorMax;
- }
- int main()
- {
- fin >> n >> m;
- for(int i = 0; i < m; i++)
- {
- int x, y;
- fin >> x >> y;
- Muchii[x][y] = 1;
- Muchii[y][x] = 1;
- }
- //cout << maxColor();
- cout << maxConnect();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement