readme

lowlinkを再帰関数を使わずに求めるのはどうするのがいいだろうかと考えてみた。

lowlink.cpp：再帰関数を使った普通のlowlink
lowlink1.cpp：再帰関数を使わないlowlink
lowlink2.cpp：再帰関数を使わないlowlinkその２

/////////////////// lowlink ///////////////////
こんな感じに囲んであるのがlowlinkを求める部分。
///////////////////////////////////////////////

lowlink1は再帰関数を使うのと大きな差はないかな。実行時間も早かった。
lowlink2はちょっと変な方針でやってみたバージョン。これは綺麗じゃないね。

一応 PKU 1144で検証済み。

lowlink.cpp

#include<cstdio>
#include<algorithm>
#define rep(i,n) for(int i = 0; i < n; i++)
#define rrep(i,n) for(int i = 1; i <= n; i++)
using namespace std;
typedef long long ll;

const int MX = 105, MG = MX*MX, INF = 1000000000;

int head[MX], next[MG], to[MG], g; bool tree[MG];
int ord[MX], low[MX], k;

/////////////////// lowlink ///////////////////
void dfs(int v){
    low[v] = ord[v] = k++;
    for(int i = head[v]; i != -1; i = next[i]){
        if(ord[to[i]] == -1){
            tree[i] = true;
            dfs(to[i]);
            low[v] = min(low[v],low[to[i]]);
        } else if(!tree[i^1]){
            low[v] = min(low[v],ord[to[i]]);
        }
    }
}
///////////////////////////////////////////////

int main(){
    int n, a, b, ans, cnt;
    char c;
    
    while(1){
        scanf("%d",&n);
        if(!n) return 0;
        
        rrep(i,n) head[i] = -1;
        g = 0;
        
        while(1){
            scanf("%d",&a);
            if(!a) break;
            while(1){
                scanf("%c",&c);
                if(c == '\n') break;
                scanf("%d",&b);
                
                next[g] = head[a]; to[g] = b; tree[g] = false; head[a] = g++;
                next[g] = head[b]; to[g] = a; tree[g] = false; head[b] = g++;
            }
        }
        
        rrep(i,n) ord[i] = -1;
        k = 0;
        dfs(1);
        
        ans = 0;
        
        rrep(i,n){
            cnt = 0;
            for(int j = head[i]; j != -1; j = next[j]){
                if(!tree[j]) continue;
                if(ord[i] <= low[to[j]]) cnt++;
            }
            if(i == 1 && cnt >= 2) ans++;
            if(i != 1 && cnt >= 1) ans++;
        }
        
        printf("%d\n",ans);
    }
    
    return 0;
}

lowlink1.cpp

#include<cstdio>
#include<stack>
#include<algorithm>
#define rep(i,n) for(int i = 0; i < n; i++)
#define rrep(i,n) for(int i = 1; i <= n; i++)
#define fi first
#define se second
using namespace std;
typedef pair<int,int> P;
typedef long long ll;

const int MX = 105, MG = MX*MX, INF = 1000000000;

int head[MX], next[MG], to[MG], g; bool tree[MG];
int ord[MX], low[MX], k;

int main(){
    int n, a, b, v, j, ans, cnt;
    char c;
    P p;
    
    while(1){
        scanf("%d",&n);
        if(!n) return 0;
        
        rrep(i,n) head[i] = -1;
        g = 0;
        
        while(1){
            scanf("%d",&a);
            if(!a) break;
            while(1){
                scanf("%c",&c);
                if(c == '\n') break;
                scanf("%d",&b);
                
                next[g] = head[a]; to[g] = b; tree[g] = false; head[a] = g++;
                next[g] = head[b]; to[g] = a; tree[g] = false; head[b] = g++;
            }
        }
        
        rrep(i,n) ord[i] = -1;
        k = 0;
        
        /////////////////// lowlink ///////////////////
        stack<P> st;
        st.push(P(1,INF));
        while(!st.empty()){
            p = st.top(); st.pop();
            v = p.fi; j = p.se;
            
            if(j == INF){
                low[v] = ord[v] = k++;
                j = head[v];
            } else {
                low[v] = min(low[v],low[to[j]]);
                j = next[j];
            }
            
            while(j != -1){
                if(ord[to[j]] == -1){
                    tree[j] = true;
                    st.push(P(v,j));
                    st.push(P(to[j],INF));
                    break;
                } else if(!tree[j^1]){
                    low[v] = min(low[v],ord[to[j]]);
                }
                j = next[j];
            }
        }
        ///////////////////////////////////////////////
        
        ans = 0;
        
        rrep(i,n){
            cnt = 0;
            for(int j = head[i]; j != -1; j = next[j]){
                if(!tree[j]) continue;
                if(ord[i] <= low[to[j]]) cnt++;
            }
            if(i == 1 && cnt >= 2) ans++;
            if(i != 1 && cnt >= 1) ans++;
        }
        
        printf("%d\n",ans);
    }
    
    return 0;
}

lowlink2.cpp

#include<cstdio>
#include<stack>
#include<algorithm>
#define rep(i,n) for(int i = 0; i < n; i++)
#define rrep(i,n) for(int i = 1; i <= n; i++)
#define fi first
#define se second
using namespace std;
typedef pair<int,int> P;
typedef long long ll;

const int MX = 105, MG = MX*MX, INF = 1000000000;

int head[MX], next[MG], to[MG], g; bool tree[MG];
int ord[MX], low[MX], k;

int main(){
    int n, a, b, j, ans, cnt;
    char c;
    P p;
    
    while(1){
        scanf("%d",&n);
        if(!n) return 0;
        
        rrep(i,n) head[i] = -1;
        g = 0;
        
        while(1){
            scanf("%d",&a);
            if(!a) break;
            while(1){
                scanf("%c",&c);
                if(c == '\n') break;
                scanf("%d",&b);
                
                next[g] = head[a]; to[g] = b; tree[g] = false; head[a] = g++;
                next[g] = head[b]; to[g] = a; tree[g] = false; head[b] = g++;
            }
        }
        
        rrep(i,n) ord[i] = -1;
        k = 0;
        
        /////////////////// lowlink ///////////////////
        stack<P> st, st2;
        st.push(P(1,g));
        while(!st.empty()){
            p = st.top(); st.pop();
            a = p.fi; j = p.se; b = to[j^1];
            
            if(ord[a] == -1){
                tree[j] = true;
                low[a] = ord[a] = k++;
                for(int i = head[a]; i != -1; i = next[i]) st.push(P(to[i],i));
                if(j != g) st2.push(P(a,j));
            } else if(!tree[j^1]){
                low[b] = min(low[b],ord[a]);
            }
        }
        while(!st2.empty()){
            p = st2.top(); st2.pop();
            a = p.fi; j = p.se; b = to[j^1];
            
            low[b] = min(low[b],low[a]);
        }
        ///////////////////////////////////////////////
        
        ans = 0;
        
        rrep(i,n){
            cnt = 0;
            for(int j = head[i]; j != -1; j = next[j]){
                if(!tree[j]) continue;
                if(ord[i] <= low[to[j]]) cnt++;
            }
            if(i == 1 && cnt >= 2) ans++;
            if(i != 1 && cnt >= 1) ans++;
        }
        
        printf("%d\n",ans);
    }
    
    return 0;
}