Задача Озборување

This message was edited 2 times. Last update was at 12/04/2012 18:00:08

Имам проблем со задачата Озборување од почетничка лани.
Ми поминува на 19/20, ми паѓа на 5тиот пример на "Runtime Error".
Еве ми го кодот:

Еве го примерот:
3
21
1 2
1 2
3 1
1 3
1 3
1 3
1 2
2 3
2 3
2 1
3 1
3 1
1 2
3 1
3 2
1 3
3 2
1 3
3 1
1 2
1 3

Треба да врати 2, мојата програма локално исто враќа 2.

Ајде помош некој ако може.

Многу броеви претураш помеѓу векторите - тест случајот е таков да бројот на елементи експоненцијално ќе расте. На пример, на крајот од програмава имаш еден вектор (covek[1].site) со 5094752 елементи.
Проверувај, во програмата, дали воопшто има потреба од додавање на нови елементи. Нешто слично на ова:

#include <iostream>
#include <set>
#include <vector>

using namespace std;

class cove
{
      public:
      vector<int> site;
      set<int> broj;
};

int main()
{
   int n,m,i,a,b,j;
   cin>>n>>m;
   cove covek[n+1];

for(i=1;i<=n;i++)
      {
            covek[i].site.push_back(i);
            covek[i].broj.insert(i);
      }

for(j=0;j<m;j++)
      {
         cin>>a>>b;

for(i=0;i<covek[a].site.size();i++)
            if (covek[b].broj.find(covek[a].site[i]) == covek[b].broj.end()) //NEW
            {
                    covek[b].broj.insert(covek[a].site[i]);
                    covek[b].site.push_back(covek[a].site[i]);
            }

for(i=0;i<covek[b].site.size();i++)
             if (covek[a].broj.find(covek[b].site[i]) == covek[a].broj.end()) //NEW
             {
                   covek[a].broj.insert(covek[b].site[i]);
                   covek[a].site.push_back(covek[b].site[i]);
             }
      }

int res=0;
      for(i=1;i<=n;i++)
     {
         if(covek[i].broj.size()>res)
         res=covek[i].broj.size();
     }

cout<<res-1<<endl;

return 0;
}

Може мало објаснување што правиш во ифовите што ги смени? Малце ми е тешко да се снајдам

This message was edited 1 time. Last update was at 12/04/2012 23:07:55

filip_bujaroski wrote:Може мало објаснување што правиш во ифовите што ги смени? Малце ми е тешко да се снајдам

set1.find(element) == set1.end() - ќе врати true, ако element не се наоѓа во множеството set1.
Така е дефиниран методот find - враќа итератор до елементот или set.end() ако елементот не постои.

Во овој случај (го разгледувам првиот if), проверуваме дали covek[a].site[i] веќе постои во covek[b].broj - што всушност означува и дали постои во векторот covek[b].site.

Јасно е

Фала многу, ова првото со set1.find не го знаев