алгоритм — связанные компоненты в неориентированных графах в Stack Overflow

Question

алгоритм — связанные компоненты в неориентированных графах в Stack Overflow

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

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

1 3
2 5
6 9

Выход:

Как есть 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;
}

-2

algorithm c++connected-components graph-theory

Решение

Другие решения

Похоже, вы должны начать с изменения на 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,

0

Источник

Accepted Answer

Давайте посмотрим, сколько ребер создано в худшем случае. это 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 если он уже существует, но я не уверен, что ваше первоначальное решение является правильным).

0