using System; using System.Collections.Generic; namespace Dag { struct Vertex{ public List neighbours; public bool visited; public bool finished; public int coins; public int coinsToEnd; public int loopsTo; public int coinsToLoop; public int time; public bool printed; public bool hasCoin; public bool printDFSD; }; class Program { static void PrintLoop(int k,int target, Vertex[] graph){ foreach(int l in graph[k].neighbours){ if(graph[l].loopsTo == target && graph[k].time < graph[l].time){ PrintLoop(l,target,graph); } } if(graph[k].hasCoin && !graph[k].printed){ Console.Write($"{k+1} "); graph[k].printed = true; graph[k].coins--; } } static void PrintDFS(int k,Vertex[] graph){ Console.WriteLine($"In PrintDFS: {k}"); graph[k].printDFSD = true; if(graph[k].hasCoin && !graph[k].printed){ graph[k].printed = true; Console.Write($"{k+1} "); } if(k==99){ Console.WriteLine($"76 loop: {graph[76].loopsTo}"); } bool chosen =false; foreach(int l in graph[k].neighbours){ if(graph[l].loopsTo == k ){ //Console.WriteLine($"PrintLoop: {l} {k}"); PrintLoop(l,k,graph); } if(k==10){ Console.WriteLine($"k coinsToEnd: {graph[k].coinsToEnd}, l coinsToEnd : {graph[l].coinsToEnd}, k coins: {graph[k].coins}"); } if((!chosen) && !graph[l].printDFSD && graph[l].coinsToEnd == graph[k].coinsToEnd - graph[k].coins ){ PrintDFS(l,graph); chosen = true; } } //Console.WriteLine($"Out PrintDFS: {k}"); } static int Earliest(Vertex[] graph, int a,int b){ if(a==-1)return b; if(b==-1)return a; return graph[a].time < graph[b].time ? a : b; } static int DFS(int k,Vertex[] graph,int time,int n){ if(k==10) Console.WriteLine($"We arrived at {k}, 98 is visited {graph[98].visited}, 98 is finished {graph[98].finished}\n"); graph[k].visited = true; graph[k].coinsToEnd = -1; graph[k].coinsToLoop = -1; graph[k].loopsTo = -1; graph[k].time = time; if(k==n-1){ graph[k].coinsToEnd = 0; } foreach(int l in graph[k].neighbours){ if(graph[l].finished){ graph[k].coinsToEnd = Math.Max(graph[l].coinsToEnd, graph[k].coinsToEnd); }else if(graph[l].visited){ if(graph[k].loopsTo==-1)graph[k].coinsToLoop=0; graph[k].loopsTo = Earliest(graph, graph[k].loopsTo, l); } else{ time = DFS(l,graph,time+1,n); graph[k].coinsToEnd = Math.Max(graph[l].coinsToEnd, graph[k].coinsToEnd); if(graph[l].loopsTo == k){ graph[k].coins += graph[l].coinsToLoop; }else if(graph[k].loopsTo==-1){ graph[k].loopsTo = graph[l].loopsTo; graph[k].coinsToLoop = graph[l].coinsToLoop; }else if(graph[l].loopsTo!=-1){ graph[k].loopsTo = Earliest(graph,graph[k].loopsTo , graph[l].loopsTo); graph[k].coinsToLoop += graph[l].coinsToLoop; } } } if(k==10){ Console.WriteLine($"coinsToEnd of 10 before: {graph[k].coinsToEnd}"); Console.WriteLine($"loopsTo of 10 before: {graph[k].loopsTo}"); } if(graph[k].loopsTo!=-1){ graph[k].coinsToLoop+=graph[k].coins; }else if(graph[k].coinsToEnd!=-1){ graph[k].coinsToEnd+=graph[k].coins; } if(k==10){ Console.WriteLine($"coinsToEnd of 10 after: {graph[k].coinsToEnd}"); } //graph[k].coinsToEnd += graph[k].coins; //if(graph[k].coinsToLoop !=-1) // graph[k].coinsToLoop += graph[k].coins; graph[k].finished = true; return time; } static void Main(string[] args) { string[] threeNumbers = Console.ReadLine().Split(' '); int n = Int32.Parse(threeNumbers[0]); int m = Int32.Parse(threeNumbers[1]); int s = Int32.Parse(threeNumbers[2]); Vertex[] graph = new Vertex[n]; for(int i =0; i(); graph[i].visited =false; graph[i].finished =false; graph[i].printed =false; graph[i].coins =0; graph[i].hasCoin =false; } for(int j =0; j0){ PrintDFS(0,graph); Console.WriteLine(); } } } }