2016-1A Problem C

Final solutions

Solution 1

// package, import, etc...

func start() {
  // read T, repeat test() T times...
}

type Node struct {
	childId   int
	bff       *Node
	isBffOf   []*Node
	distance  int
	component *Component
	isInCycle bool
}

type Component struct {
	entry      *Node
	cycleSize  int
	isPartOf   *Component
	cycleEntry *Node
}

func test() {
	stdout.Flush()
	os.Stderr.Write([]byte{'\n'})
	var N int
	mustReadLineOfInts(&N)
	bffs := mustReadLineOfIntsIntoArray()
	assert(len(bffs) == N)
	for i := 0; i < N; i++ {
		bffs[i]--
		assert(bffs[i] >= 0 && bffs[i] < N && bffs[i] != i)
	}
	childsLeft := make(map[int]bool)
	for i := 0; i < N; i++ {
		childsLeft[i] = true
	}
	childNodes := make([]*Node, N)
	components := make([]Component, 0)
	for len(childsLeft) > 0 {
		var childId int
		for childId, _ = range childsLeft {
			break
		}
		components = append(components, Component{})
		cp := &components[len(components)-1]
		entry := buildChild(cp, bffs, childNodes, childsLeft, childId, 0)
		cp.entry = entry
		if cp.isPartOf == nil {
			debug(fmt.Sprintf("Component with child %d has cycle size %d starting %v", cp.entry.childId+1, cp.cycleSize, cp.cycleEntry.childId+1))
		}
	}
	maxCycleSize := 0
	twoCyclesSzie := 0
	for _, c := range components {
		if c.isPartOf != nil {
			continue
		}
		if c.cycleSize > 2 {
			if maxCycleSize < c.cycleSize {
				maxCycleSize = c.cycleSize
			}
		} else {
			assert(c.cycleSize == 2)
			entry := c.cycleEntry
			assert(c.cycleEntry != nil)
			current := entry
			ct := 0
			for {
				ct++
				current.isInCycle = true
				current = current.bff
				if current == entry {
					break
				}
			}
			assert(ct == 2)
			ct = 0
			tl := 0
			for {
				ct++
				tl += tailSize(current)
				current = current.bff
				if current == entry {
					break
				}
			}
			assert(ct == 2)
			ct = 0
			cSize := 2 + tl
			twoCyclesSzie += cSize
		}
	}
	maxCSize := maxCycleSize
	if twoCyclesSzie > maxCSize {
		maxCSize = twoCyclesSzie
	}
	fmt.Fprintf(stdout, "%d\n", maxCSize)
}

func buildChild(component *Component, bffs []int, childNodes []*Node, childsLeft map[int]bool, childId int, distance int) *Node {
	if childNodes[childId] != nil {
		_, exist := childsLeft[childId]
		assert(!exist)
		cn := childNodes[childId]
		if cn.component == component {
			assert(component.cycleSize == 0)
			component.cycleSize = distance - cn.distance
			component.cycleEntry = cn
			return cn
		} else {
			component.isPartOf = cn.component
			// We are not in a cycle
			return cn
		}
	}
	_, exist := childsLeft[childId]
	assert(exist)
	delete(childsLeft, childId)
	childNodes[childId] = &Node{
		childId:   childId,
		bff:       nil,
		isBffOf:   make([]*Node, 0),
		distance:  distance,
		component: component,
		isInCycle: false,
	}
	bff := buildChild(component, bffs, childNodes, childsLeft, bffs[childId], distance+1)
	childNodes[childId].bff = bff
	bff.isBffOf = append(bff.isBffOf, childNodes[childId])
	if bff.component != component {
		childNodes[childId].component = bff.component
		assert(bff.component == component.isPartOf)
	}
	return childNodes[childId]
}

func tailSize(node *Node) int {
	maxTailSize := 0
	for _, t := range node.isBffOf {
		assert(t.component == node.component)
		if t.isInCycle {
			continue
		}
		ts := tailSize(t) + 1
		if maxTailSize < ts {
			maxTailSize = ts
		}
	}
	return maxTailSize
}

// boilerplate omitted...

Solution 2

// package, import, etc...

func start() {
  // read T, repeat test() T times...
}

func test() {
	var N int
	mustReadLineOfInts(&N)
	bff := mustReadLineOfIntsIntoArray()
	assert(len(bff) == N)
	for i := 0; i < N; i++ {
		bff[i]--
	}

	largestCycleSize := 0
	isTwoSizedCycles := make([]bool, N)
	tailLengths := make([]int, N)
	visited := make([]bool, N)
	for i := 0; i < N; i++ {
		if visited[i] {
			continue
		}
		visited[i] = true
		// start dfs on each vertex
		cur := i
		iter := 0
		len := 0
		newVisited := make([]bool, N)
		for {
			if bff[bff[cur]] == cur {
				isTwoSizedCycles[cur] = true
				isTwoSizedCycles[bff[cur]] = true
				if tailLengths[cur] < len {
					tailLengths[cur] = len
				}
				break
			}
			len++
			iter++
			cur = bff[cur]
			if cur == i {
				break
			}
			newVisited[cur] = true
			if iter > N+1 {
				len = 0
				break
			}
		}
		if largestCycleSize < len {
			largestCycleSize = len
		}
		if len > 0 {
			for i := 0; i < N; i++ {
				if newVisited[i] {
					visited[i] = true
				}
			}
		}
	}

	twoSizedCycleCircleSize := 0
	for i := 0; i < N; i++ {
		if isTwoSizedCycles[i] {
			twoSizedCycleCircleSize += tailLengths[i] + 1
		}
	}

	if twoSizedCycleCircleSize > largestCycleSize {
		fmt.Fprintf(stdout, "%d\n", twoSizedCycleCircleSize)
	} else {
		fmt.Fprintf(stdout, "%d\n", largestCycleSize)
	}
}

// boilerplate omitted...

Sample test cases given in question

4
4
2 3 4 1
4
3 3 4 1
4
3 3 4 3
10
7 8 10 10 9 2 9 6 3 3

Other files

5
6
6 5 2 2 6 3
4
4 3 2 1
3
2 1 1
6
2 1 1 2 4 4
4
4 1 2 3

Case #1: 4
Case #2: 4
Case #3: 3
Case #4: 5
Case #5: 4