Реализация Сильно подключенных компонентов для целых чисел в файле

Question

Я работаю над реализацией программы с сильно связанными компонентами из входного файла чисел. Я знаю алгоритм о том, как это сделать, но с трудом реализуя его в python.

СИЛЬНО СВЯЗАННЫХ-КОМПОНЕНТЫ (G) 1. запустить DFS на G, чтобы вычислить время закончить 2. вычислить G « 3. запустить DFS на G», но при выборе, какой узел Вист сделать так, чтобы уменьшения времени закончить (как вычисляется на шаге 1) 4. выходной вершины каждого дерева в глубину первого леса шага 3 в качестве отдельного компонента, подключенного сильно

файл выглядит следующим образом:

5 5 
1 2 
2 4 
2 3 
3 4 
4 5 

Первая строка - нет. узлов и ребер. Остальные строки - это два целых числа u и v, разделенные пробелом, что означает направленное ребро от узла u до узла v. Выход должен быть сильно связанным компонентом и отсутствием этих компонентов.

DFS(G) 
1 for each vertex u in G.V 
2  u.color = WHITE 
3  u.π = NIL 
4 time = 0 
5 for each vertex u in G.V 
6  if u.color == WHITE 
7   DFS-VISIT(G, u) 

DFS-VISIT(G, u) 
1 time = time + 1 // white vertex u has just been discovered 
2 u.d = time 
3 u.color = GRAY 
4 for each v in G.adj[u] 
5  if v.color == WHITE 
6   v.π = u 
7   DFS-VISIT(G, u) 
8 u.color = BLACK // blacken u; it is finished 
9 time = time + 1 
10 u.f = time 

В приведенном выше алгоритме, как я должен пройти обратный график, чтобы найти SCC.

Answer 1

Здесь реализовано в Python.

Обратите внимание, что я строю G и G 'одновременно. Мой DFS также изменен. В массиве visited хранится, в каком компоненте находится каждый узел. Кроме того, DFS получает аргумент sequence, то есть порядок, в котором тестируются узлы. В первой DFS мы передаем xrange (n), но во второй раз мы передаем обратный (порядок) из первого выполнения.

Программа будет что-то вроде:

3 
[1, 1, 1, 2, 3] 

В этом выходе, мы имеем 3 сильно связные компоненты, с 3 первых узлов в одном компоненте, а остальные два с одним компонентом каждого.

def DFSvisit(G, v, visited, order, component): 
    visited[v] = component 
    for w in G[v]: 
     if not visited[w]: 
      DFSvisit(G, w, visited, order, component) 
    order.append(v); 

def DFS(G, sequence, visited, order): 
    components = 0 
    for v in sequence: 
     if not visited[v]: 
      components += 1 
      DFSvisit(G, v, visited, order, components) 

n, m = (int(i) for i in raw_input().strip().split()) 

G = [[] for i in xrange(n)] 
Gt = [[] for i in xrange(n)] 
for i in xrange(m): 
    a, b = (int(i) for i in raw_input().strip().split()) 
    G[a-1].append(b-1) 
    Gt[b-1].append(a-1) 

order = [] 
components = [0]*n 

DFS(G, xrange(n), [0]*n, order) 
DFS(Gt, reversed(order), components, []) 

print max(components) 
print components 

Answer 2

class graphSCC: 
    def __init__(self, graplist): 
     self.graphlist = graphlist 
     self.visitedNode = {} 
     self.SCC_dict = {}  
     self.reversegraph = {} 

def reversegraph(self): 
    for edge in self.graphlist: 
     line = edge.split("\t") 
     self.reverseGraph.setdefault(strip("\r"), []).append() 
    return self.reverseGraph 

def dfs(self): 
    SCC_count = 0 
    for x in self.reversegraph.keys(): 
     self.visitednode[x] = 0 

    for x in self.reversegraph.keys(): 
     if self.visitednode[x] == 0: 
      count += 1 
      self.explore(x, count) 

def explore(self, node, count): 
    self.visitednode[node] = 1 

    for val in self.reversegraph[node]: 
     if self.visitednode[val] == 0: 
      self.explore(val, count) 
    self.SCC_dict.setdefault(count, []).append(node) 

length = 0 
node = 0 
for x in graph.SCC_dict.keys(): 
    if length < len(graph.SCC_dict[x]): 
     length = len(graph.SCC_dict[x]) 
     node = x 

длина требуемый ответ