Topological Sort without modifying the graph or marking edges
Instead of seting a 'mark' flag;

 node.Marked = true;


You can maintain a set of marked nodes in a hashtable or similar;

 hashTable[node] = true;


You now have to pass the hash table around, but it's O(n) for space and O(1) to check if a node is marked.