using System; using System.Collections.Generic; namespace Dag{ class Program{ struct Vertex{ public List outGoing; public List inGoing; } struct Graph{ public Vertex[] v; public Graph(int length){ v = new Vertex[length]; for(int i=0; i< length; i++){ v[i].outGoing = new List(); v[i].inGoing = new List(); } } public int length{ get {return v.Length;} } public override string ToString(){ String str=""; for(int i=0; i vertices, int k){ visited[k] =true; foreach(int l in g.v[k].outGoing){ if(!visited[l]){ DFSFinishingTimeOrderHelper(g,visited,vertices,l); } } vertices.Add(k); } static int[] DFSFinishingTimeOrder(Graph g,bool[] visited){ List vertices= new List(); DFSFinishingTimeOrderHelper(g,visited,vertices,0); return(vertices.ToArray()); } static void DFS_VisitTransposeHelper(Graph g,bool[] discovered, List vertices, int k,bool[] visited){ discovered[k] =true; foreach(int l in g.v[k].inGoing){ if(!discovered[l]&&visited[l]){ DFS_VisitTransposeHelper(g,discovered,vertices,l,visited); } } vertices.Add(k); } static List DFS_VisitTranspose(Graph g,int u,bool[] discovered,bool[] visited){ //bool[] discovered = new bool[g.length]; List vertices= new List(); DFS_VisitTransposeHelper(g,discovered,vertices,u,visited); return(vertices); } static List> SCC(Graph g){ //Call DFS and compute finish time f[u] for each u bool[] visited = new bool[g.length]; int[] vertices = DFSFinishingTimeOrder(g,visited); bool[] discovered = new bool[g.length]; List> components = new List>(); //while some vertex in GT //is not-discovered do for(int i=vertices.Length-1; i>=0 ; i--){ //Console.WriteLine(i); //u ← not-discovered vertex with the latest f[u] int u = vertices[i]; if(discovered[u])continue; //Call DFS-VISIT(u) on GT components.Add(DFS_VisitTranspose(g,u,discovered,visited)); } return components; } static void OptimalDFS(Graph g, bool[] visited, int[] optimal, int[] coins, bool[] noDeadEnd, int k,int end){ visited[k] = true; //the finish can't be a dead end if(k== end){ noDeadEnd[k]=true; optimal[k] = coins[k]; } for(int i=0; i> components){ if(!noDeadEnd[0])return; int new_k; for(int k = 0; k>=0;k=new_k){ //Console.WriteLine(k); foreach(int c in components[k]) if(coins[c]>0) Console.Write($"{c+1} "); new_k =-1; for(int i=0; i> components = SCC(g); //for(int i=0;i=0&&componentPerVertex[l]>=0&&componentPerVertex[l] != componentPerVertex[k]){ componentGraph.addEdge(componentPerVertex[k],componentPerVertex[l]); } } } //Console.WriteLine(componentGraph); int [] optimal = new int[componentGraph.length]; bool [] noDeadEnd = new bool[componentGraph.length]; Console.WriteLine(Optimal(componentGraph, coinsPerComponent,optimal,noDeadEnd,componentPerVertex[n-1])); PrintPath(componentGraph,coinsPerComponent,coins,optimal,noDeadEnd,components); } } }