第28章 图和深度优先搜索
2020-04-13 本文已影响0人
得力小泡泡
1、连通块的数量
算法分析
并查集
把所有具有连通性质的点形成一个集合，set集合记录的是所有连通块的根结点，从1到n枚举所有点，把所有点的根结点全部放进set中，由于set有去重效果，因此set的大小即是连通块的数量
时间复杂度 )
并查集的复杂度接近O(1)
Java 代码
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Main {
static int N = 20010;
static int[] p = new int[N];
static Set<Integer> set= new HashSet<Integer>();
static int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int m = scan.nextInt();
for(int i = 1;i <= n;i ++) p[i] = i;
for(int i = 0;i < m;i ++)
{
int a = scan.nextInt();
int b = scan.nextInt();
a = find(a);
b = find(b);
if(a != b)
{
p[a] = b;
}
}
for(int i = 1;i <= n;i ++)
{
set.add(find(i));
}
System.out.println(set.size());
}
}
2、下午茶时间
算法分析
并查集
将所有具有连通性质的点归并到一个集合，枚举所有询问的点a,b，若a和b在同一个集合，则返回"Y"，否则返回"N"
时间复杂度
并查集的复杂度接近O(1)
Java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N = 1010;
static int n,m,q;
static int[] p = new int[N];
static int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s1 = br.readLine().split(" ");
n = Integer.parseInt(s1[0]);
m = Integer.parseInt(s1[1]);
q = Integer.parseInt(s1[2]);
for(int i = 1;i <= n;i ++) p[i] = i;
for(int i = 0;i < m;i ++)
{
String[] s2 = br.readLine().split(" ");
int a = Integer.parseInt(s2[0]);
int b = Integer.parseInt(s2[1]);
a = find(a);
b = find(b);
if(a != b) p[a] = b;
}
for(int i = 0;i < q;i ++)
{
String[] s3 = br.readLine().split(" ");
int a = Integer.parseInt(s3[0]);
int b = Integer.parseInt(s3[1]);
a = find(a);
b = find(b);
if(a == b) System.out.println("Y");
else System.out.println("N");
}
}
}
3、家谱
算法分析
树形dp
先根据题目要求构建出一棵树，记录每个点是否有father，若该点没有father，则该点就是根结点root，从root往下dfs，记录每个点具有多少个直系后代
注意：这题输入输出很大，需要用buffer来输入输出
时间复杂度
Java 代码
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
public class Main {
static int N = 100010;
static int[] h = new int[N];
static int[] e = new int[N];
static int[] ne = new int[N];
static boolean[] father = new boolean[N];
static int idx = 0;
static int[] ans = new int[N];
static void add(int a,int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
static int dfs(int root)
{
int res = 0;
for(int i = h[root];i != -1;i = ne[i])
{
int j = e[i];
res += dfs(j) + 1;
}
ans[root] = res;
return res;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
Arrays.fill(h, -1);
for(int i = 0;i < n - 1;i ++)
{
String[] s1 = br.readLine().split(" ");
int a = Integer.parseInt(s1[0]);
int b = Integer.parseInt(s1[1]);
add(a,b);
father[b] = true;
}
int root = 0;
for(int i = 1;i <= n;i ++)
{
if(!father[i])
{
root = i;
break;
}
}
dfs(root);
for(int i = 1;i <= n;i ++)
{
log.write(ans[i] + "\n");
}
log.flush();
log.close();
}
}
4、联合权值
算法分析
需要注意的地方，如果1号点和3号点是联合点，需要对联合权值算两遍，即(1,3)，(3,1)
如图所示，假设一个结点的出边点(即儿子和父亲)的权值分别是
求出以该点为中心的所有联合权值，因为隔着该点，该点的儿子和儿子和父亲的距离均是等于2，因此该点的所有联合权值的式子是(为了方便计算先把自己加上，再减去自己)
即
因此从任意点开始出发，dfs遍历所有位置，dfs过程中：
-
d1记录当前点的出边点的最大权值 -
d2记录当前点的出边点的第二大权值 -
sum记录当前点的 -
psum记录当前点的
因此该点求得总和联合值是，最大联合权值是
时间复杂度
Java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static int N = 200010,M = N * 2;
static int[] h = new int[N];
static int[] e = new int[M];
static int[] ne = new int[M];
static int[] w = new int[N];
static int idx = 0;
static int n;
static long maxv = 0,res = 0;//maxv记录最大值，res记录总和
static int mod = 10007;
static void add(int a,int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
static void dfs(int u,int father)
{
int d1 = 0;
int d2 = 0;
long sum = 0;//(x1 + x2 + ... + xn)
long psum = 0;//(x1^2 + x2^2 + ... + xn^2)
for(int i = h[u];i != -1;i = ne[i])
{
int j = e[i];
if(w[j] > d1)
{
d2 = d1;
d1 = w[j];
}
else if(w[j] > d2)
{
d2 = w[j];
}
sum += w[j];
psum += w[j] * w[j];
if(j == father) continue;
dfs(j,u);
}
res = (res + sum * sum - psum) % mod;
maxv = Math.max(maxv,d1 * d2);
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
Arrays.fill(h, -1);
for(int i = 0;i < n - 1;i ++)
{
String[] s1 = br.readLine().split(" ");
int a = Integer.parseInt(s1[0]);
int b = Integer.parseInt(s1[1]);
add(a,b);
add(b,a);
}
String[] s2 = br.readLine().split(" ");
for(int i = 1;i <= n;i ++)
{
w[i] = Integer.parseInt(s2[i - 1]);
}
dfs(1,-1);
System.out.println(maxv + " " + res);
}
}
