• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    迪恩网络公众号

C++ UnionFind类代码示例

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

本文整理汇总了C++中UnionFind的典型用法代码示例。如果您正苦于以下问题:C++ UnionFind类的具体用法?C++ UnionFind怎么用?C++ UnionFind使用的例子?那么恭喜您, 这里精选的类代码示例或许可以为您提供帮助。



在下文中一共展示了UnionFind类的20个代码示例,这些例子默认根据受欢迎程度排序。您可以为喜欢或者感觉有用的代码点赞,您的评价将有助于我们的系统推荐出更棒的C++代码示例。

示例1: feasible2

bool feasible2(int i, UnionFind &uf) {
    int a = A[i];
    bool a_is_half_square = isHalfSquare(a);
    if (a_is_half_square) {
        if (deg[a] > 0 || cnt[a] > 1) return false;
    }
    cnt[a]++;
    seen[num_seen++] = a;
    for (int k = 1; k <= 512; k++) {
        int64_t b = k*k - a;
        if (b == a) continue;
        if (b > 0 && b < MAXN && cnt[b] > 0) {
            if (uf.find(a) == uf.find(b) ||
                uf.find(a+MAXN) == uf.find(b+MAXN)) return false;
            if (isHalfSquare(b)) {
                if (cnt[b] > 1) return false;
                deg[b]++;
            }
            if (a_is_half_square) deg[a]++;
            uf.join(a, b+MAXN);
            uf.join(a+MAXN, b);
        }
    }
    return true;
}
开发者ID:atubo,项目名称:codeforces,代码行数:25,代码来源:P3940.cpp


示例2: main

int main(){
    int t,n,cont;
    cin>>t;
    string a,b;
    map<string,int> convers;
    UnionFind u;

    while (t-->0){
        cin>>n;
        int p,q;

        u.reset(2*n+1);
        convers.clear();
        cont = 1;

        for (int i=0;i<n;i++){
            cin>>a>>b;
            if (!convers.count(a))convers[a] = cont++;
            if (!convers.count(b))convers[b] = cont++;
            p = convers[a], q = convers[b];
            u.unionSet(p,q);
            cout<<u.getSize(p)<<endl;
        }
    }
}
开发者ID:lucassf,项目名称:UVA-Solutions,代码行数:25,代码来源:11503.cpp


示例3: initPercolate

  void initPercolate(){
	 int topPseudoVarIndex = dim*dim;
	 int bottomPseudoVarIndex = topPseudoVarIndex +1;
	 Ufobj = new UnionFind(dim*dim+2); /* 0 to dim*dim -1 is regular grid var */
	 for(int i =0;i< dim;i++){ /* top row */
	   Ufobj->DoUnion(topPseudoVarIndex,i);
	 }	
	 for(int i =dim*(dim-1);i< dim*dim;i++){ /* bottom row */
	   Ufobj->DoUnion(bottomPseudoVarIndex,i);
	 }	
  }
开发者ID:dpant,项目名称:Algorithm,代码行数:11,代码来源:Percolation.cpp


示例4: reset2

void reset2(int k, UnionFind &uf) {
    for (int i = num_seen-1; i >= 0; i--) {
        int a = seen[i];
        cnt[a] = 0;
        deg[a] = 0;
        uf.makeSet(a);
        uf.makeSet(a+MAXN);
    }
    cnt[A[k]] = 1;
    seen[0] = A[k];
    num_seen = 1;
}
开发者ID:atubo,项目名称:codeforces,代码行数:12,代码来源:P3940.cpp


示例5: visitTarjan

void visitTarjan(const Graph &g, int u, int w,
        vector<Query> &qs, vector<int> &color,
        vector<int> &ancestor, UnionFind &uf) {
    ancestor[ uf.root(u) ] = u;
    FOR(e, g[u]) if (e->dst != w) {
        visitTarjan(g, e->dst, u, qs, color, ancestor, uf);
        uf.unionSet( e->src, e->dst );
        ancestor[ uf.root(u) ] = u;
    }
    color[u] = 1;
    FOR(q, qs) {
        int w = (q->v == u ? q->u : q->u == u ? q->v : -1);
        if (w >= 0 && color[w]) q->w = ancestor[ uf.root(w) ];
    }
开发者ID:hamko,项目名称:procon,代码行数:14,代码来源:d.cpp


示例6: find

 /**
  * This method finds the representative element of the UF structure,
  * while performing the path compression.
  * @return the representative UnionFind of the group.
  */
 UnionFind * find(){
     if (parent == nullptr)
         parent = this;
     if (parent != this)
         parent = parent->find();
     return parent;
 }
开发者ID:hoyleb,项目名称:fof_cluster_finder,代码行数:12,代码来源:galaxy_class.hpp


示例7: kruskal

int kruskal() {
    sort(es, es + E, comp);

    UnionFind *unionfind = new UnionFind();
    unionfind->init(V);
    int res = 0;

    for (int i = 0; i < E; i++) {
        edge e = es[i];
        if (!unionfind->same(e.from, e.to)) {
            unionfind->unite(e.from, e.to);
            res += e.cost;
        }
    }
    return res;
}
开发者ID:y-kamiya,项目名称:test,代码行数:16,代码来源:kruskal.cpp


示例8: numIslands2

    vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
        UnionFind uni;
        vector<int> res;

        for (int i=0; i<positions.size(); ++i) {
            auto pos = positions[i];
            int r = pos.first;
            int c = pos.second;

            S.insert(positions[i]);
            uni.add(positions[i]);

            if (S.find(pair<int,int>(r-1, c)) != S.end()) {
                uni.merge(pair<int,int>(r-1,c), pair<int,int>(r,c));
            }
            if (S.find(pair<int,int>(r, c+1)) != S.end()) {
                uni.merge(pair<int,int>(r,c+1), pair<int,int>(r,c));
            }
            if (S.find(pair<int,int>(r+1, c)) != S.end()) {
                uni.merge(pair<int,int>(r+1,c), pair<int,int>(r,c));
            }
            if (S.find(pair<int,int>(r, c-1)) != S.end()) {
                uni.merge(pair<int, int>(r, c - 1), pair<int, int>(r, c));
            }
            res.push_back(uni.countSet());
        }
        return res;
    }
开发者ID:pengmessi,项目名称:LeetCode2016,代码行数:28,代码来源:LC305.cpp


示例9: main

int main (int argc, char** argv)
{
    if (argc <=1) { 
        printf("Usage: ./union <problem_number> \n");
        exit(1);
    }

    int problem_no = atoi(argv[1]);
    UnionFind* uf = new UnionFind (10);

    switch(problem_no) {
        case 0:
        case 1:
            uf->type = QFIND;
            printf("Problem number 1: ");
            /* Q1 union find */
            uf->join(1,4);
            uf->join(9,4);
            uf->join(6,8);
            uf->join(2,1);
            uf->join(0,4);
            uf->join(3,7);
            break;
        case 2:
            printf("Problem number 2: ");
            uf->type = WT_QUNION;
             /* Q2 Weighted quick union */
            uf->wt_join(7,9);
            uf->wt_join(9,4);
            uf->wt_join(7,0);
            uf->wt_join(8,1);
            uf->wt_join(3,7);
            uf->wt_join(5,6);
            uf->wt_join(5,1);
            uf->wt_join(3,8);
            uf->wt_join(2,6);
            break;
        default:
            assert(0 && "Invalid problem number");
            break;
    }

    uf->print();
    return 0;
}
开发者ID:mrasquinha,项目名称:algos,代码行数:45,代码来源:union.cpp


示例10: solve

void solve() {
    int ans = 0;
    UnionFind uf = UnionFind(N * 3);

    for(int i = 0; i < K; ++i) {
        int x = X[i] - 1, y = Y[i] - 1;
        if(x < 0 || N <= x || y < 0 || N <= y) {
            ++ans;
        }
        else if(D[i] == 1) {
            if(uf.same(3 * x, 3 * y + 1) || uf.same(3 * x, 3 * y + 2))
                ++ans;
            else
                for(int j = 0; j < 3; ++j)
                    uf.unite(3 * x + j, 3 * y + j);
        }
        else {
            if(uf.same(3 * x, 3 * y + 2) || uf.same(3 * x, 3 * y))
                ++ans;
            else
                for(int j = 0; j < 3; ++j)
                    uf.unite(3 * x + j, 3 * y + (j + 1) % 3);
        }
    }
    printf("%d\n", ans);
}
开发者ID:blue-jam,项目名称:blue-jam.github.io,代码行数:26,代码来源:poj1182.cpp


示例11: main

int main() {
  UnionFind uf;
  uf.init(5);

  assert(!uf.is_same_set(1, 3));
  assert(!uf.is_same_set(0, 4));
  assert(uf.no_disjoint_sets() == 5);

  uf.union_set(1, 2);
  uf.union_set(2, 3);
  uf.union_set(3, 4);

  assert(uf.size_of_set(2) == 4);
  assert(!uf.is_same_set(0, 3));
  assert(uf.is_same_set(1, 4));
  assert(uf.no_disjoint_sets() == 2);  

  return 0;
}
开发者ID:freskov,项目名称:competitive_programming,代码行数:19,代码来源:union_find.cpp


示例12: main

int main()
{
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    int tc;
    scanf("%d",&tc);
    while(tc--)
    {
        int no_friends,f,i=0,a,b;
        string str1,str2;
        char f1[21],f2[21];
        scanf("%d",&f);
        map<string,int>names;
        map<string,int>::iterator it;
        UnionFind uf;
        while(f--)
        {
            scanf("%s %s",f1,f2);
            str1=string(f1);
            str2=string(f2);
            if((it=names.find(str1))==names.end())
            {
                names.insert(make_pair(str1,i));
                uf.add(a=i++);
            }
            else a=it->second;
            if((it=names.find(str2))==names.end())
            {
                names.insert(make_pair(str2,i));
                uf.add(b=i++);
            }
            else b=it->second;

            printf("%d\n",uf.union_set(a,b));
        }
    }
    return 0;

}
开发者ID:sillychip,项目名称:uva,代码行数:39,代码来源:uva_11503.cpp


示例13: UnionFind

void Graph::remove_cycles() {
  /* Pouzijeme Kruskaluv algoritmus s implementaci vyuzivajici strukturu
   Unionfind. Zde usnadnen tim, ze vsechny hrany maji stejnou vahu. */
  UnionFind *uf = new UnionFind(vertex_count);
  
  // V matici incidence projdeme vsechny hrany
  for (int i = 0; i < vertex_count; i++) {
    for (int j = i; j < vertex_count; j++) {
      if (!get(i, j))
        continue;
      /* Pokud jsme v ramci doposud prozkoumanych hran nenasli cestu
       mezi i a j, poznamenejme si do unionfind struktury, ze nyni
       uz ji mame. V opacnem pripade vyhodime z grafu hranu mezi i a j,
       at nemame cyklus. */      
      if (!uf->find(i, j)) {
        uf->do_union(i, j);
      } else {
        unset(i, j);
      }
    }
  }
}
开发者ID:mlazovla,项目名称:PPR2015-STR,代码行数:22,代码来源:graph.cpp


示例14: crete_union_find

UnionFind* crete_union_find(const std::string& file_name)
{
    int size = 0;
    i__pair *int_list = nullptr;

    parse_input_file(file_name,size,&int_list);
    if(int_list != nullptr && size != 0)
    {
        UnionFind *uFind = new UnionFind();
        uFind->printData();
        for(int index = 0; index < size ; index++)
        {
            if(!uFind->is_connected(int_list[index].first_number, int_list[index].second_number))
            {
                uFind->m_createUnion(int_list[index].first_number, int_list[index].second_number);
            }
        }
        delete[] int_list;
        return uFind;
    }
    return nullptr;
}
开发者ID:uknowit,项目名称:Algorithms,代码行数:22,代码来源:QuickFind.cpp


示例15: main

int main(void)
{
    cin.sync_with_stdio(false);
    int N, M;
    cin >> N >> M;

    vector<vector<int>> speaker_to_langs(N);
    vector<char> seen_langs(M);

    UnionFind uf;
    uf.Init(M);

    
    REP(n,N) {
        int k;
        cin >> k;
        vector<int> langs(k);
        REP(k1,k) {
            int l;
            cin >> l; --l;
            langs[k1] = l;
            seen_langs[l] = 1;
        }
开发者ID:minus9d,项目名称:programming_contest_archive,代码行数:23,代码来源:c.s.cpp


示例16: executar

	void executar(SolucaoEdgeSet &s, auxEdgeStruct arestas []) {

		for(int i = 0; i < NUMOBJETIVOS; i++) {
			s.setObj(i,0.0);
		}

		uf.clear();
		
		// coloca NUMEROVERTICES-1 arestas do grafo sem formar ciclo
		int cont = 0, edge = 0;
		while (cont < NUMEROVERTICES-1) {

			// anda ate a proxima aresta que pode ser inserida
			while (uf.sameClass(arestas[edge].a,arestas[edge].b)) edge++;

			// coloca a aresta na solucao
			s.edges[cont][0] = arestas[edge].a;
			s.edges[cont][1] = arestas[edge].b;
			s.setObj(0,s.getObj(0)+f(0,s.edges[cont][0],s.edges[cont][1]));
			s.setObj(1,s.getObj(1)+f(1,s.edges[cont][0],s.edges[cont][1]));
			uf.unionClass( arestas[edge].a, arestas[edge].b );
			cont++;
		}
		// assert (s.confereArestas());
	}
开发者ID:islamifelipe,项目名称:AGMO_exactAlgoritms,代码行数:25,代码来源:LexKruskal.cpp


示例17: Build

  /// Build tracks for a given series of pairWise matches
  void Build( const PairWiseMatches &  map_pair_wise_matches)
  {
    // 1. We need to know how much single set we will have.
    //   i.e each set is made of a tuple : (imageIndex, featureIndex)
    typedef std::set<indexedFeaturePair> SetIndexedPair;
    SetIndexedPair allFeatures;
    // For each couple of images list the used features
    for (PairWiseMatches::const_iterator iter = map_pair_wise_matches.begin();
      iter != map_pair_wise_matches.end();
      ++iter)
    {
      const size_t & I = iter->first.first;
      const size_t & J = iter->first.second;
      const std::vector<IndMatch> & vec_FilteredMatches = iter->second;

      // Retrieve all shared features and add them to a set
      for( size_t k = 0; k < vec_FilteredMatches.size(); ++k)
      {
        allFeatures.emplace(I,vec_FilteredMatches[k].i_);
        allFeatures.emplace(J,vec_FilteredMatches[k].j_);
      }
    }

    // 2. Build the 'flat' representation where a tuple (the node)
    //  is attached to an unique index.
    map_node_to_index.reserve(allFeatures.size());
    unsigned int cpt = 0;
    for (const auto & feat : allFeatures)
    {
      map_node_to_index.emplace_back(feat, cpt);
      ++cpt;
    }
    // Sort the flat_pair_map
    map_node_to_index.sort();
    // Clean some memory
    allFeatures.clear();

    // 3. Add the node and the pairwise correpondences in the UF tree.
    uf_tree.InitSets(map_node_to_index.size());

    // 4. Union of the matched features corresponding UF tree sets
    for (PairWiseMatches::const_iterator iter = map_pair_wise_matches.begin();
      iter != map_pair_wise_matches.end();
      ++iter)
    {
      const auto & I = iter->first.first;
      const auto & J = iter->first.second;
      const std::vector<IndMatch> & vec_FilteredMatches = iter->second;
      for (const IndMatch & match : vec_FilteredMatches)
      {
        const indexedFeaturePair pairI(I, match.i_);
        const indexedFeaturePair pairJ(J, match.j_);
        // Link feature correspondences to the corresponding containing sets.
        uf_tree.Union(map_node_to_index[pairI], map_node_to_index[pairJ]);
      }
    }
  }
开发者ID:kjaylee,项目名称:openMVG,代码行数:58,代码来源:tracks.hpp


示例18: Build

  /// Build tracks for a given series of pairWise matches
  void Build( const matching::PairWiseMatches &  map_pair_wise_matches)
  {
    // 1. We need to know how much single set we will have.
    //   i.e each set is made of a tuple : (imageIndex, featureIndex)
    std::set<indexedFeaturePair> allFeatures;
    // For each couple of images list the used features
    for ( const auto & iter : map_pair_wise_matches )
    {
      const auto & I = iter.first.first;
      const auto & J = iter.first.second;
      const std::vector<matching::IndMatch> & vec_FilteredMatches = iter.second;

      // Retrieve all shared features and add them to a set
      for ( const auto & cur_filtered_match : vec_FilteredMatches )
      {
        allFeatures.emplace(I,cur_filtered_match.i_);
        allFeatures.emplace(J,cur_filtered_match.j_);
      }
    }

    // 2. Build the 'flat' representation where a tuple (the node)
    //  is attached to a unique index.
    map_node_to_index.reserve(allFeatures.size());
    uint32_t cpt = 0;
    for (const auto & feat : allFeatures)
    {
      map_node_to_index.emplace_back(feat, cpt);
      ++cpt;
    }
    // Sort the flat_pair_map
    map_node_to_index.sort();
    // Clean some memory
    allFeatures.clear();

    // 3. Add the node and the pairwise correpondences in the UF tree.
    uf_tree.InitSets(map_node_to_index.size());

    // 4. Union of the matched features corresponding UF tree sets
    for ( const auto & iter : map_pair_wise_matches )
    {
      const auto & I = iter.first.first;
      const auto & J = iter.first.second;
      const std::vector<matching::IndMatch> & vec_FilteredMatches = iter.second;
      for (const matching::IndMatch & match : vec_FilteredMatches)
      {
        const indexedFeaturePair pairI(I, match.i_);
        const indexedFeaturePair pairJ(J, match.j_);
        // Link feature correspondences to the corresponding containing sets.
        uf_tree.Union(map_node_to_index[pairI], map_node_to_index[pairJ]);
      }
    }
  }
开发者ID:autosquid,项目名称:openMVG,代码行数:53,代码来源:tracks.hpp


示例19: argument

    bool argument(int s) {
        memset(&uf, 0, sizeof(uf));
        memset(link, 0, sizeof(link));
        memset(type, 0, sizeof(type));
        q.clear();
        q.push_back(s);
        type[s] = EVEN;

        while (!q.empty()) {
            int u = q.front();
            q.pop_front();

            for (int v : G[u]) {
                if (!type[v]) {
                    type[v] = ODD;
                    link[v] = u;

                    if (match[v]) {
                        type[match[v]] = EVEN;
                        q.push_back(match[v]);
                    } else {
                        int x = v;
                        while (link[x] != s) {
                            int a = link[x];
                            int b = match[a];
                            match[x] = a;
                            match[a] = x;
                            x = b;
                        }

                        match[s] = x;
                        match[x] = s;

                        return true;
                    }
                } else if (type[v] == EVEN &&
                           uf.find(u) != uf.find(v)) {
                    int p = lca(u, v);

                    if (uf.find(u) != p)
                        link[u] = v;
                    if (uf.find(v) != p)
                        link[v] = u;

                    process(u, p);
                    process(v, p);
                }
            }
        }

        return false;
    }
开发者ID:riteme,项目名称:test,代码行数:52,代码来源:copy1.cpp


示例20: add_node

inline void add_node(IntervalTree::Node *x) {
    for (size_t i = 0; i < x->edges.size(); i++) {
        Edge *e = x->edges[i];

        e->idu = uf.find_root(e->u);
        e->idv = uf.find_root(e->v);
        if (e->idu == e->idv) {
            e->idu = e->idv = 0;
            continue;
        }

        uf.link(e->idu, e->idv);
    }
}
开发者ID:riteme,项目名称:test,代码行数:14,代码来源:fake.cpp



注:本文中的UnionFind类示例由纯净天空整理自Github/MSDocs等源码及文档管理平台,相关代码片段筛选自各路编程大神贡献的开源项目,源码版权归原作者所有,传播和使用请参考对应项目的License;未经允许,请勿转载。


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
C++ UniqueChars类代码示例发布时间:2022-05-31
下一篇:
C++ UniformParameterPtr类代码示例发布时间:2022-05-31
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap