Блог пользователя adamantium

Автор adamantium, 10 лет назад, По-английски

How can i find the articulation point in a graph using DFS algorithm ??? Any pseudo code or source code will be helpful for me......

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
10 лет назад, # |
Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится
inline void dfs(int node){
    bool flag=0;
    int child=0;
    start[node] = ++timer;
    low[node] = start[node];
    foreach(it,V[node]){
        if(!start[*it]){
            dfs(*it);
            ++child;
            low[node] = min(low[node],low[*it]);
            if (low[*it] >= start[node])
                flag = true;
        }
        else
            low[node] = min(low[node],start[*it]);
    }
    if((node==1 && child > 1) || (node != 1 && flag))
        articulation_points.pb(node); //node is an AP.
}

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

Here is code:

//MAXN = maximum points in the graph
vector<int> g[MAXN];
bool used[MAXN];
int timer, tin[MAXN], fup[MAXN];

void dfs (int v, int p = -1) {
    used[v] = true;
    tin[v] = fup[v] = timer++;
    int children = 0;
    for (size_t i=0; i<g[v].size(); ++i) {
        int to = g[v][i];
        if (to == p)  continue;
        if (used[to])
            fup[v] = min (fup[v], tin[to]);
        else {
            dfs (to, v);
            fup[v] = min (fup[v], fup[to]);
            if (fup[to] >= tin[v] && p != -1)
                //v is articulation point
                ++children;
        }
    }
    if (p == -1 && children > 1)
        //v is articulation point
        }

int main() {
    int n;
    // read n and g 
    timer = 0;
    for (int i=0; i<n; ++i)
        used[i] = false;
    dfs (0);
}
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Could someone give me the non-recursive implementation of the procedure to find the number of articulation points in a graph?