链接: https://pan.baidu.com/s/1pzMI6BD6R-yX7gYhAJG6Ew
提取码: sw8r
using System;
using System.Collections.Generic;
using System.Linq;
namespace ConsoleApp1
{
class Program
{
static int num;
static void Main(string[] args)
{
num = int.Parse(Console.ReadLine()) ;
Graph g = new Graph() { VertexCount = num };
while (true)
{
string s = Console.ReadLine();
if (s == null) break;
string[] words = s.Split();
int from = int.Parse(words[0])-1, to = int.Parse(words[1])-1;
g.AddEdge(from, to);
}
List<List<int>> sccs = g.Kosaraju();
Console.Write(String.Join("\n", sccs.Select(i => string.Join(" ", i.Select(v => v + 1)))));
}
class Edge { public int Begin { get; set; } public int End { get; set; } }
class Graph
{
public Dictionary<int, List<Edge>> _adjacentEdges = new Dictionary<int, List<Edge>>();
public int VertexCount { get; set; }
public IEnumerable<int> Vertices { get { return _adjacentEdges.Keys; } }
public IEnumerable<Edge> Edges
{
get { return _adjacentEdges.Values.SelectMany(e => e); }
}
public int EdgeCount { get { return this.Edges.Count(); } }
public void AddEdge(int begin, int end)
{
if (!_adjacentEdges.ContainsKey(begin))
{
var edges = new List<Edge>();
_adjacentEdges.Add(begin, edges);
}
_adjacentEdges[begin].Add(new Edge { Begin = begin, End = end });
}
public List<List<int>> Kosaraju()
{
Stack<int> stack = new Stack<int>();
// Mark all the vertices as not visited (For first DFS)
bool[] visited = new bool[VertexCount];
for (int i = 0; i < visited.Length; i++)
visited[i] = false;
// Fill vertices in stack according to their finishing times
for (int i = 0; i < visited.Length; i++)
if (!visited[i])
FillOrder(i, visited, stack);
// Create a reversed graph
Graph reversedGraph = Transpose();
// Mark all the vertices as not visited (For second DFS)
for (int i = 0; i < visited.Length; i++)
visited[i] = false;
List<List<int>> sccs = new List<List<int>>();
// Now process all vertices in order defined by Stack
while (stack.Count > 0)
{
// Pop a vertex from stack
int v = stack.Pop();
// Print Strongly connected component of the popped vertex
if (!visited[v])
{
List<int> scc = new List<int>();
reversedGraph.DFS(v, visited, scc);
sccs.Add(scc);
}
}
return sccs;
}
void DFS(int v, bool[] visited, List<int> scc)
{
visited[v] = true;
scc.Add(v);
if (_adjacentEdges.ContainsKey(v))
{
foreach (var edge in _adjacentEdges[v])
{
if (!visited[edge.End])
DFS(edge.End, visited, scc);
}
}
}
void FillOrder(int v, bool[] visited, Stack<int> stack)
{
// Mark the current node as visited and print it
visited[v] = true;
// Recur for all the vertices adjacent to this vertex
if (_adjacentEdges.ContainsKey(v))
{
foreach (var edge in _adjacentEdges[v])
{
if (!visited[edge.End])
FillOrder(edge.End, visited, stack);
}
}
// All vertices reachable from v are processed by now,
// push v to Stack
stack.Push(v);
}
Graph Transpose()
{
Graph g = new Graph() { VertexCount = num };
foreach (var edge in this.Edges)
{
g.AddEdge(edge.End, edge.Begin);
}
return g;
}
}
}
}
using System;
using System.Collections.Generic;
namespace ConsoleApp1
{
class Graph
{
int num;
List<int>[] edge;
List<int>[] reverse;
public Graph()
{
num = int.Parse(Console.ReadLine());
edge = new List<int>[num + 1];
reverse = new List<int>[num + 1];
for (int i = 1; i <= num; ++i)
{
edge[i] = new List<int>();
reverse[i] = new List<int>();
}
while (true)
{
string s = Console.ReadLine();
if (s == null)
break;
string[] words = s.Split();
int from = int.Parse(words[0]);
int to = int.Parse(words[1]);
edge[from].Add(to);
reverse[to].Add(from);
}
}
private LinkedList<int> orderedVertex;
public void Kosaraju()
{
orderedVertex = new LinkedList<int>();
bool[] visited = new bool[num + 1];
for (int i = 1; i <= num; i++)
{
if (!visited[i])
{
FirstPassDFS(i, visited);
}
}
Array.Clear(visited, 0, num + 1);
foreach (int u in orderedVertex)
{
if (!visited[u])
{
var scc = new List<int>();
SecondPassDFS(u, visited, scc);
Console.WriteLine(string.Join(" ", scc));
}
}
}
private void SecondPassDFS(int u, bool[] visited, List<int> output)
{
visited[u] = true;
output.Add(u);
foreach (var v in edge[u])
{
if (!visited[v])
{
SecondPassDFS(v, visited, output);
}
}
}
// Run first pass DFS on reversed edges
private void FirstPassDFS(int u, bool[] visited)
{
visited[u] = true;
foreach (var v in reverse[u])
{
if (!visited[v])
{
FirstPassDFS(v, visited);
}
}
orderedVertex.AddFirst(u);
}
}
}
main函数里这样调用 new Graph().Kosaraju(); 命令行运行ConsoleApp1.exe <in1.txt
代码直接翻译自伪代码 https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm ，无需太多注释。
over