HashMap在求解最大连通分量中的应用

1 基于DFS的连通分量数求解算法

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;
import java.util.Set;

public class Main {
	static HashMap<Integer,Set> map=new HashMap<Integer,Set>();
	static int n; //顶点数
	static int e; //边数
	static boolean[] flag; //标记顶点是否已访问
	static int count=0; //连通分量数
	
	public static void main(String[] args) {
		makeGraph();
		flag=new boolean[n];
		for(int i=0;i<n;i++) {
			if(!flag[i]) {
				dfs(i);
				count++;
			}
		}
		System.out.println(count);
	}
	
	static void makeGraph() {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		e=sc.nextInt();
		for(int i=0;i<e;i++) {
			int a=sc.nextInt();
			int b=sc.nextInt();
			if(!map.containsKey(a)) {
				Set<Integer> set=new HashSet<Integer>();
				set.add(b);
				map.put(a,set);
			}else {
				map.get(a).add(b);
			}
			if(!map.containsKey(b)) {
				Set<Integer> set=new HashSet<Integer>();
				set.add(a);
				map.put(b,set);
			}else {
				map.get(b).add(a);
			}
		}
	}
	
	static void dfs(int index) {
		flag[index]=true;
		if(!map.containsKey(index)) {
			return;
		}
		Iterator<Integer> iter=map.get(index).iterator();
		while(iter.hasNext()) {
			int v=iter.next();
			if(!flag[v]) {
				dfs(v);
			}
		}
	}
}

2 基于分类的连通分量数求解算法

import java.util.HashMap;
import java.util.Scanner;

class Edge{ //边
	int a;
	int b;
	Edge(int a,int b){
		this.a=a;
		this.b=b;
	}
}

public class Main {
	static HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
	static int n; //顶点数
	static int e; //边数
	static Edge[] edge;
	static boolean[] flag; //标记是否为非孤立点
	static int count=0; //连通分量数
	
	public static void main(String[] args) {
		makeGraph();
		classify();
		System.out.println(count);
	}
	
	static void makeGraph() {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		e=sc.nextInt();
		edge=new Edge[e];
		flag=new boolean[n];
		for(int i=0;i<e;i++) {
			int a=sc.nextInt();
			int b=sc.nextInt();		
			edge[i]=new Edge(a,b);
			flag[a]=true;
			flag[b]=true;
		}
	}
	
	static void classify() {
		for(int i=0;i<e;i++) {
			if(map.containsKey(edge[i].a)) {
				map.put(edge[i].b, map.get(edge[i].a));
			}else if(map.containsKey(edge[i].b)) {
				map.put(edge[i].a, map.get(edge[i].b));
			}else {
				count++;
				map.put(edge[i].a, count);
				map.put(edge[i].b, count);
			}
		}
		for(int i=0;i<n;i++) {
			if(!flag[i]) {
				count++;
			}
		}
	}
}