- 浏览: 105766 次
- 性别:
- 来自: 广州
最新评论
-
xinhemei:
我试了试,发现gmail和163的不行。好像ajax请求失败了 ...
jQuery实现邮箱自动登录 -
酒鬼_yuan:
我正在找 谢谢了
关于yui的学习
package middle; import java.io.BufferedInputStream; import java.util.Scanner; /** * poj2524 * 并查集的最简应用 * 只需要合并,并统计当前合集数就行了 * 好长时间啊!!! * 4622MS * @author NC */ public class Poj2524 { public static void main(String[] args) { final int MAXSIZE = 50001; Scanner scan = new Scanner(new BufferedInputStream(System.in)); int caseI = 1;//记录case int max = 0; while (scan.hasNext()) { int n = scan.nextInt(); int m = scan.nextInt(); if (n == 0 && m == 0) { break; } DisjointSet dj = new DisjointSet(MAXSIZE); int count = 0; for (int i = 0; i < m; i++) { int a = scan.nextInt(); int b = scan.nextInt(); int ra = dj.find(a); int rb = dj.find(b); if (ra != rb) { dj.union(ra, rb); count++; } } max = n - count; String result = "Case " + caseI + ": " + max; System.out.println(result); caseI++; } } } class DisjointSet { protected int n; protected int[] parent; protected int[] rank; public DisjointSet(int n) { this.n = n; init(n); } protected void init(int n) { this.parent = new int[this.n + 1]; this.rank = new int[this.n + 1];//用来记录元素是否已经添加过了 for (int i = 1; i <= n; i++) { parent[i] = i; rank[i] = 1; } } protected int find(int x) {//返回第x号元素的根结点 if (parent[x] != x) { parent[x] = find(parent[x]); } return parent[x]; } protected void union(int ra, int rb) {//参数是根结点 if (rank[ra] > rank[rb]) { parent[rb] = ra; } else if (rank[ra] < rank[rb]) { parent[ra] = rb; } else { rank[rb]++; parent[ra] = rb; } } }
发表评论
-
Poj3126
2010-05-29 22:07 1197import java.io.BufferedIn ... -
poj3125简单模拟
2010-05-25 11:44 916import java.io.BufferedInputS ... -
还是水
2010-05-24 12:53 728import java.io.BufferedInputS ... -
Poj3085再水一下
2010-05-24 12:28 817import java.io.BufferedInputS ... -
Poj3673超水题
2010-05-24 12:12 815package easy; import java. ... -
Poj3278 广度优先搜索
2010-05-22 23:24 1281import java.io.BufferedInputS ... -
合唱队形
2010-05-09 21:45 2100#include <stdio.h> #incl ... -
动态规划经典问题 石子合并
2010-05-09 21:45 6050我们学校的oj的 #include & ... -
poj3199 高精
2010-05-09 21:44 920import java.io.BufferedInputS ... -
poj1002 郁闷的电话号码
2010-05-08 23:48 1225import java.io.BufferedInputS ... -
poj1298 无语。。。
2010-04-24 23:24 972import java.io.BufferedInputStr ... -
poj1017 装箱问题 简单贪心
2010-04-18 16:56 2318import java.io.BufferedInpu ... -
poj1042 枚举+贪心算法
2010-04-18 00:45 1758import java.io.BufferedInputS ... -
zoj3197 Google Book 贪心算法
2010-04-15 23:54 1333#include <stdio.h> #defi ... -
Poj2453 an easy program
2010-04-09 00:19 828/* * To change this template, ... -
poj2299 递归与分治策略
2010-04-02 23:38 1394package hard; import java.io ... -
poj1723 数学问题
2010-04-02 15:31 987package middle; import jav ... -
Poj1308 并查集
2010-03-18 15:21 1655package middle; import jav ... -
poj1405 高精
2010-02-28 11:09 1327import java.io.BufferedInputS ... -
poj1979 深度遍历
2010-02-27 20:56 1253问题重述 问题描述: ...
相关推荐
poj2492 A Bug's Life并查集应用的扩展,希望可以给大家带来用处
POJ 1988 并查集。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
并查集基础 acm 算法 poj oi 并查集基础.ppt
POJ1089 并查集可以解决 并查集加路径压缩
这份代码用C++实现了经典算法并查集,来源于poj题目1182
poj 1611 The Suspects 代码 并查集的应用
数据结构并查集的相关资料,包括几篇并查集的论文,还有POJ上面几道关于并查集的题目的源代码
poj 食物链代码.带权并查集,关键是找到其中的一些关系式.
2. bool nodePath (bstNode* pRoot, int value, std::vector*>& path) 3. { 6
poj题目分类,适合acmer学习研究 ...9.数据结构 //并查集、堆 10.博弈论 //表示举例 非主流算法: 1.送分题 2.构造 3.高精度 4.几何 5.排序 6.日期/时间处理 (这类题目相当多的) 7.数学方法
利用并查集判断环路,以及快速排序计算最小生成树
//http://poj.org/problem?id=1611 #include using namespace std; const int maxn = 30010; int f[maxn],num[maxn],n,m; int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); } int main() { while(cin...
hdu 1914稳定婚姻 sgu176 有源汇的上下界 求最小满足的流 poj 2230 递归求欧拉回路 poj 2985 bst模板 poj2723 2-sat验证,二分答案 ...poj2832 并查集边的计算 sgu218 hcraft 二分图匹配验证 二分答案
主流算法: 1.搜索 //回溯 2.DP(动态规划) 3.贪心 4.图论 //Dijkstra、最小生成树、网络...9.数据结构 //并查集、堆 10.博弈论 1、 排序 2、 搜索、回溯、遍历 3、历法 4、 枚举 5、 数据结构的典型算法 6、 动态规划
对于LCA问题,有不少解法,这儿提供了tarjan算法,这是一种离线算法,读入所有输入然后一并处理,并且利用并查集的思想,从根节点开始DFS,对每一个DFS的节点,先把他的父亲节点指向本身,没访问完一个子节点,然后...
2.最小生成树(先写个prim,kruscal要用并查集,不好写) 3.大数(高精度)加减乘除 4.二分查找. (代码可在五行以内) 5.叉乘、判线段相交、然后写个凸包. 6.BFS、DFS,同时熟练hash表(要熟,要灵活,代码要简) ...
并查集 堆 哈希表 DFS BFS 快速幂 背包问题 区间DP 区间问题 绝对值不等式 DP课 寒假每日一题 基础班 提高班 POJ 大二 2019 新生赛 蓝桥杯模拟 蓝桥杯学习 bfs 大数 dfs/抽象dfs 逻辑 测试 栈/递归 清华oj入门
7.3 并查集 151 7.4 树状数组 152 7.5 点树 154 7.6 STL 156 7.7 离散化 157 8.图论 158 8.0 2-SAT 158 8.2 寻找Euler回路 163 8.3 拓扑排序 163 8.4 差分约束系统 164 8.5 笛卡尔树 165 8.6 LCA和RMQ 167 8.7 割...
2.4.4 并查集 2.5 它们其实都是“图” 2.5.1 图是什么 2.5.2 图的表示 2.5.3 图的搜索 2.5.4 最短路问题 2.5.5 最小生成树 2.5.6 应用问题 2.6 数学问题的解题窍门 2.6.1 辗转相除法 2.6.2 有关素数的基础算法 2.6.3...