Альтернативный алгоритм для первого поиска глубины

Question

Проблема связана с первым поиском глубины в ориентированном графе, чтобы найти все узлы, которые могут быть достигнуты с определенного узла. Решение, приведенное ниже, дает неверный результат для кодека. Но я не могу найти ни одного тестового примера, для которого это могло бы привести к другому результату, который мог бы использовать обычный алгоритм DFS.

Я знаю, что могу прямо реализовать правильный алгоритм, чтобы получить правильный результат, но я хочу узнать, почему мое решение было неправильным, чтобы я не повторил его в будущем. Пожалуйста, помогите мне определить, что не так с этим решением. Код прокомментирован объяснить мой подход

#include <iostream> 
#include <algorithm> 
#include <vector> 

using namespace std; 

typedef long long int lli; 
vector <lli> g[1000+5]; // the adjacency list 1 indexed 
void dfs(lli j, lli i); 

int main(){ 
    lli n, m, k, a, b; 
    // n = number of nodes 
    // m = number of relations 
    // k = multiplication factor 
    cin >> n >> m >> k; 
    while(m--){ 
     // a,b means a is dependent upon b (directed graph) 
     cin >> a >> b; 
     g[a].push_back(b); 
    } 

    for(lli j = 1; j <= n; j++) 
    for(lli i = 0; i < g[j].size(); i++){ 
     dfs(j, g[j][i]); // adds dependencies of g[j][i] 
         // to adjacency list of j 
    } 

    // ans is the minimum no of nodes dependent on a particular node 
    lli ans = g[1].size(); 
    for(lli i = 1; i <= n; i++){ 
     if(g[i].size() < ans) 
     ans = g[i].size(); 
    } 

    cout << (ans+1)*k <<"\n"; 
} 

void dfs(lli j, lli i){ 
    // adding dependencies of a node to itself 
    // would result in an infinite loop? 
    if(i != j){ 
     for(lli k = 0; k < g[i].size(); k++){ 
      // a node is not dependent on itself 
      if(g[i][k]!=j && find(g[j].begin(), g[j].end(), g[i][k])==g[j].end()){ 
      g[j].push_back(g[i][k]); 
      dfs(j, g[i][k]); 
      } 
     }  
    } 
}` 

ссылка для задачи: problem

ссылку для правильного решения: correct solution

Answer 1

Ваша проблема заключается в том, что вы не знаете разновременных ребер, которые являются возможно с заданной проблемой, в противном случае это выглядит правильно. Взгляните на этот тестовый пример:

2 4 1 
1 2 
1 2 
2 1 
2 1 

Ваша программа вернет 3, но есть только 2 вершины!

Сказав это, я хотел бы добавить, что я не согласен с решением образца: Он говорит, что время работы будет O(N^2), которая не является правдой, потому что он начинает N глубину каждый с затратами на O(N+M), таким образом, в результате чего O(N*(N+M)) с N=10^3 и M=10^6 не изменится в срок 0.01 секунд!

На самом деле эта проблема может быть решена в O(N+M) с использованием алгоритмов обнаружения сильно связанных компонентов.