связанные компоненты в неориентированных графах в С++

Я хотел подсчитать количество групп в неориентированных графах в С++. Я пытался использовать bfs, но безуспешно. Мне дали диапазон чисел [L, R] (или подумайте об этих диапазонах как о количестве вершин), и я нужно найти количество групп. Как мне это сделать?

Например, если у меня есть (ввод):

1 3
2 5
6 9

Выход:

2

Так как есть 2 группы.

Мой код:

bool visited[MAX];
vector<int> v[MAX];
int solve(int x)
{
  queue<int> q;int ans=0;
  q.push(x);
  if(v[x].empty())
  {
      ans++;
  }
  while(!q.empty())
  {
      int curr = q.front();
      visited[curr] = true;
      q.pop();
      for(int i = 0; i < v[curr].size(); i ++)
        {
            if(!visited[v[curr][i]])
            {
                q.push(v[curr][i]);
                visited[v[curr][i]] = true;
            }
        }
        if(v[curr].empty()) ans++;
  }
  return ans;
}
int main()
{
    int t;scanf("%d",&t);

    while(t--)
    {
        int l,r,n,ans=0,min_,max_=0;
        scanf("%d",&n);
        for(int i = 0; i < n; i ++)
            visited[i] = false;
        for(int j=0;j<n;j++)
        {
            scanf("%d",&l);scanf("%d",&r);
            for(int i=l;i<r;i++)
            {
                v[i].push_back(i+1);
                 min_ = min(min_,i);
                max_ = max(max_,i+1);
            }
        }

        printf("%d\n",solve(min_));
    }
    return 0;
}

c++ algorithm graph-theory connected-components
person wen_dy    schedule 06.01.2015    source источник
comment
Но это было безуспешно. Что пошло не так? Ваша программа дала сбой? Это дало неверный вывод?   -  person kraskevich    schedule 06.01.2015
comment
@ user111 Похоже, у вас другое представление о том, как определять графики. Обычно они определяются набором std::pair<int>, где каждый элемент пары представляет узел. Ваш ввод 1->3, 2->5, 6->9, и вы говорите, что сделаете 2 графика? Чтобы было понятно, что должно получиться 3 графика, вы согласны с этим, верно?   -  person Jonathan Mee    schedule 06.01.2015
comment
@JonathanMee Он создаст графики: 1-›2-›3-›4-›5 и 6-›7-›8-›9 . Итак, 2 графика.   -  person wen_dy    schedule 06.01.2015
comment
@IloveCoding Я получил ошибку выполнения (SIGSEGV). Мне просто нужно знать, как считать группы в неориентированном графе.   -  person wen_dy    schedule 06.01.2015
comment
@ user111 Насколько большими могут быть n, L и R?   -  person kraskevich    schedule 06.01.2015
comment
Вы имеете в виду как это? И это? А это codechef.com/JAN15/problems/ONEKING?   -  person beaker    schedule 06.01.2015
comment
@beaker Для меня они выглядят иначе. Это о нахождении количества связанных компонентов, последние 2 ссылки о чем-то вроде вершинного покрытия.   -  person kraskevich    schedule 06.01.2015
comment
@beaker Первый касается поиска наибольшего набора сегментов. Вторые два касаются нахождения минимального количества точек, соединяющих все сегменты. Этот вопрос связан, но касается нахождения количества несвязанных наборов сегментов. (И, что особенно важно, совсем не о графиках.)   -  person Jonathan Mee    schedule 06.01.2015

Ответы (2)


arrow_upward
0
arrow_downward

Давайте посмотрим, сколько ребер создается в худшем случае. Это N * (MAX_R - MIN_L), что равно 10^5 * 2000 при заданных ограничениях. У вашей программы заканчивается память и возникает ошибка времени выполнения. Требуется более эффективный алгоритм. Вот простое решение, которое использует только O(MAX_R) памяти и
O(N + MAX_R) времени.

vector<int> start(MAX_R + 1);
vector<int> end(MAX_R + 1);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
    int low;
    int high;
    cin >> low >> high;
    start[low]++;
    end[high]++;
}
int res = 0;
int sum = 0;
for (int pos = 0; pos <= MAX_R; pos++) {
    if (sum == 0 && start[pos] > 0)
        res++;
    sum += start[pos] - end[pos];
}
cout << res << endl;

В этой задаче нет необходимости в bfs или каких-либо других графовых алгоритмах.

Вы можете исправить свое исходное решение, избегая нескольких ребер в графе (нет необходимости создавать ребро от i до i + 1, если оно уже существует, но я не уверен, правильно ли ваше исходное решение).

person kraskevich    schedule 06.01.2015
comment
Итак, здесь MAX_R равно 2000. ? @ILoveCoding - person wen_dy; 06.01.2015
comment
Я получаю 1 в качестве вывода для ввода, который я указал выше, но это должно быть 2 . @ILoveCoding - person wen_dy; 06.01.2015
comment
@ usr111 Я отредактировал свой ответ пару минут назад. Была ошибка, теперь работает нормально. - person kraskevich; 06.01.2015
comment
Я думаю, что он все еще содержит некоторые ошибки .. @ILoveCoding - person wen_dy; 06.01.2015
comment
@ user111 Почему ты так думаешь? У вас есть тестовый пример, который не проходит? - person kraskevich; 06.01.2015

arrow_upward
0
arrow_downward

Похоже, вы должны начать с изменения на vector<pair<int,int>> v;. Затем для заполнения v вы должны использовать:

scanf("%d", &l);scanf("%d", &r);
v.push_back(make_pair(l, r);

Тогда ваша функция должна стать чем-то вроде:

int solve(){
    vector<pair<int, int>> results;

    for(auto& vIndex : v){
        auto resultIndex = find_if(results.begin(), results.end(), [vIndex](const pair<int, int>& i){return vIndex.first >= i.first && vIndex.first <= i.second || vIndex.second >= i.first && vIndex.second <= i.second;});

        if(resultIndex == results.end()){
            results.push_back(vIndex);
        }else{
            resultIndex->first = min(vIndex.first, resultIndex->first);
            resultIndex->second = max(vIndex.second, resultIndex->second);
        }
    }
    return results.size();
}

Вы можете увидеть это в действии здесь: http://ideone.com/MDQBOr Просто жестко закодируйте нужные входные данные в v .

person Jonathan Mee    schedule 06.01.2015
comment
@ user111 Стоит отметить, что вы строите не график, а дерево сегментов. Мой подход - грубая сила, если вам нужно быстро решить эту проблему, лучше использовать дерево, описанное в ссылке. - person Jonathan Mee; 06.01.2015