-2

C++ で無向グラフのグループ数を数えたかったのですが、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;
}
4

2 に答える 2

0

に変更することから始める必要があるようです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/MDQBOor必要な入力を にハードコードするだけですv。

于 2015-01-06T18:25:09.333 に答える
0

最悪の場合にいくつのエッジが作成されるかを見てみましょう。それは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元のソリューションが正しいかどうかはわかりません)。

于 2015-01-06T17:49:58.133 に答える