ARC114-B Special Subsets

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("2");
            WillReturn.Add("2 1");
            //1
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2");
            WillReturn.Add("1 1");
            //1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("3");
            WillReturn.Add("1 2 3");
            //7
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    const int Hou = 998244353;

    static Dictionary<int, int> mToNodeDict = new Dictionary<int, int>();

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] FArr = InputList[1].Split(' ').Select(pX => int.Parse(pX)).ToArray();

        for (int I = 0; I <= FArr.GetUpperBound(0); I++) {
            mToNodeDict[I + 1] = FArr[I];
        }

        int CycleCnt = DeriveCycleCnt();

        long Answer = 1;
        for (int I = 1; I <= CycleCnt; I++) {
            Answer *= 2;
            Answer %= Hou;
        }
        Answer--;
        if (Answer < 0) {
            Answer += Hou;
        }
        Console.WriteLine(Answer);
    }

    // ファンクショナルグラフでの閉路数を返す
    static int DeriveCycleCnt()
    {
        int CycleCnt = 0;

        var BeforeVisitedSet = new HashSet<int>();

        // 未訪問ノードから深さ優先探索
        foreach (int EachNode in mToNodeDict.Keys) {
            if (BeforeVisitedSet.Contains(EachNode)) continue;

            bool Result = HasCycleHelperExecDFS(EachNode, BeforeVisitedSet);
            if (Result) {
                CycleCnt++;
            }
        }
        return CycleCnt;
    }

    // DeriveCycleCntのヘルパメソッドで、深さ優先探索を行う
    struct JyoutaiDef_HasCycle
    {
        internal int CurrNode;
    }
    static bool HasCycleHelperExecDFS(int pStaNode, HashSet<int> pBeforeVisitedSet)
    {
        var CurrVisitedSet = new HashSet<int>();

        JyoutaiDef_HasCycle WillPush;
        WillPush.CurrNode = pStaNode;

        var Stk = new Stack<JyoutaiDef_HasCycle>();
        Stk.Push(WillPush);
        while (Stk.Count > 0) {
            JyoutaiDef_HasCycle Popped = Stk.Pop();

            int CurrNode = Popped.CurrNode;
            CurrVisitedSet.Add(CurrNode);

            int ChildNode = mToNodeDict[CurrNode];

            // 前回までのDFSで訪問済の場合
            if (pBeforeVisitedSet.Contains(ChildNode)) {
                pBeforeVisitedSet.UnionWith(CurrVisitedSet);
                return false;
            }

            // 今回のDFSで再訪したら閉路あり
            if (CurrVisitedSet.Add(ChildNode) == false) {
                pBeforeVisitedSet.UnionWith(CurrVisitedSet);
                return true;
            }

            WillPush.CurrNode = ChildNode;
            Stk.Push(WillPush);
        }
        return false;
    }
}

解説

ファンクショナルグラフでして、
問題文の条件から下記を導出できます。

全ての a ∈ T について f(a) ∈ T 
∴ 移動元ノードはいずれかのノードの移動先になっている

全ての a,b ∈ T について
a != b ⇒ f(a) != f(b)
対偶は同値なので
f(a) = f(b)  ⇒ a = b
∴ 移動先ノードが同じなら移動元ノードは同じ
∴ 入次数が2以上のノードが存在しない

考察すると、サイクルの数が5なら
(2の5乗)-1 が解だと分かるので、
DFSでサイクルの数を取得してます。