高级农民
- 积分
- 2737
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2017-6-18
- 最后登录
- 1970-1-1
|
本帖最后由 magicsets 于 2018-2-16 06:46 编辑
先计算SCC,然后将每个SCC合并到一个节点,这样原图就简化为一个DAG(有向无环图),然后求这个简化后的DAG中有多少in-degree为0的点就可以了吧
不过实际写的时候可以不做“合并”这一步,参考代码:- import java.util.ArrayList;
- import java.util.Collections;
- import java.util.HashMap;
- import java.util.HashSet;
- import java.util.Stack;
- public class Solution {
- public static void main(String[] args) {
- Graph g1 = new Graph();
- // O ---> O
- // ^ |
- // | v
- // O <--- O ---> O
- g1.addEdge(1, 2);
- g1.addEdge(2, 3);
- g1.addEdge(3, 4);
- g1.addEdge(3, 5);
- g1.addEdge(4, 1);
- System.out.println("Result = " + g1.zeroInDegreeNodesWithRegardToSCC());
- // Result = 1
- Graph g2 = new Graph();
- // O ---> O
- // |
- // v
- // O
- g2.addEdge(1, 2);
- g2.addEdge(1, 3);
- System.out.println("Result = " + g2.zeroInDegreeNodesWithRegardToSCC());
- // Result = 1
- Graph g3 = new Graph();
- // O <--- O
- // ^
- // |
- // O
- g3.addEdge(2, 1);
- g3.addEdge(3, 1);
- System.out.println("Result = " + g3.zeroInDegreeNodesWithRegardToSCC());
- // Result = 2
- Graph g4 = new Graph();
- // O <--- O O ---> O
- // | ^ ^ |
- // v | | v
- // O ---> O O ---> O
- g4.addEdge(1, 2);
- g4.addEdge(2, 3);
- g4.addEdge(3, 4);
- g4.addEdge(4, 1);
- g4.addEdge(5, 6);
- g4.addEdge(6, 7);
- g4.addEdge(7, 8);
- g4.addEdge(8, 5);
- System.out.println("Result = " + g4.zeroInDegreeNodesWithRegardToSCC());
- // Result = 2
- }
- }
- class Graph {
- private HashSet<Integer> nodes = new HashSet<Integer>();
- private HashMap<Integer, HashSet<Integer>> edges =
- new HashMap<Integer, HashSet<Integer>>();
- public void addNode(int node) {
- nodes.add(node);
- }
- public void addEdge(int src, int dst) {
- nodes.add(src);
- nodes.add(dst);
- HashSet<Integer> list = edges.get(src);
- if (list == null) {
- list = new HashSet<Integer>();
- edges.put(src, list);
- }
- list.add(dst);
- }
- public int zeroInDegreeNodesWithRegardToSCC() {
- SCCReverseIndex sccIndex = new SCCReverseIndex(getSCC());
- HashSet<Integer> exNodes = new HashSet<Integer>();
- for (Integer node : nodes) {
- HashSet<Integer> neighbors = edges.get(node);
- if (neighbors != null) {
- for (Integer nb : neighbors) {
- if (!sccIndex.areStronglyConnected(node, nb) ||
- !sccIndex.isHeader(nb)) {
- exNodes.add(nb);
- }
- }
- }
- }
- int count = 0;
- for (Integer node : nodes) {
- if (!exNodes.contains(node)) {
- ++count;
- }
- }
- return count;
- }
- // ------------------------------------------------------------------------
- // 用Tarjan算法计算Strongly Connected Components.
- // https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
- private enum Status {
- kUnvisited,
- kVisiting,
- kVisited
- }
- private static class SCCInfo {
- int index;
- int lowlink;
- Status status = Status.kUnvisited;
- void init(int index) {
- this.index = index;
- this.lowlink = index;
- }
- }
- private static class Context {
- int index = 0;
- Stack<Integer> stack = new Stack<Integer>();
- HashMap<Integer, SCCInfo> sccInfo = new HashMap<Integer, SCCInfo>();
- ArrayList<HashSet<Integer>> sccs = new ArrayList<HashSet<Integer>>();
- }
- public ArrayList<HashSet<Integer>> getSCC() {
- Context ctx = new Context();
- for (Integer node : nodes) {
- ctx.sccInfo.put(node, new SCCInfo());
- }
- for (Integer node : nodes) {
- if (ctx.sccInfo.get(node).status == Status.kUnvisited) {
- tarjanSCC(node, ctx);
- }
- }
- return ctx.sccs;
- }
- private void tarjanSCC(int node, Context ctx) {
- SCCInfo info = ctx.sccInfo.get(node);
- info.init(ctx.index++);
- ctx.stack.push(node);
- info.status = Status.kVisiting;
- HashSet<Integer> neighbors = edges.get(node);
- if (neighbors != null) {
- for (Integer nb : neighbors) {
- SCCInfo nbInfo = ctx.sccInfo.get(nb);
- if (nbInfo.status == Status.kUnvisited) {
- tarjanSCC(nb, ctx);
- info.lowlink = Math.min(info.lowlink, nbInfo.lowlink);
- } else {
- info.lowlink = Math.min(info.lowlink, nbInfo.index);
- }
- }
- }
- if (info.lowlink == info.index) {
- HashSet<Integer> scc = new HashSet<Integer>();
- int curr;
- do {
- curr = ctx.stack.pop();
- ctx.sccInfo.get(curr).status = Status.kVisited;
- scc.add(curr);
- } while (curr != node);
- ctx.sccs.add(scc);
- }
- }
- }
- // 用于查询node在哪个SCC中的索引
- class SCCReverseIndex {
- private HashMap<Integer, Integer> index = new HashMap<Integer, Integer>();
- public SCCReverseIndex(ArrayList<HashSet<Integer>> sccs) {
- for (HashSet<Integer> scc : sccs) {
- Integer label = Collections.min(scc);
- for (Integer node : scc) {
- index.put(node, label);
- }
- }
- }
- public boolean areStronglyConnected(int lhs, int rhs) {
- return index.get(lhs) == index.get(rhs);
- }
- public boolean isHeader(int node) {
- return index.get(node) == node;
- }
- }
复制代码 |
|