ZOJ 1311 Network 割頂

裸的連通圖求割點

[cpp]  #include <cstdio>  
#include <algorithm>  
#include <cstring>  
#include <iostream>  
#include <vector>  
using namespace std; 
#define N 103  
vector<int> g[N]; 
int n, low[N], dfn[N], f[N]; 
bool vis[N]; 
 
void dfs(int u, int depth, const int &root) { 
    dfn[u] = low[u] = depth; 
    vis[u] = true; 
    int cnt = 0; 
    for (int i=0; i<g[u].size(); i++) { 
        int v = g[u][i]; 
        if (!vis[v]) { 
            cnt++; 
            dfs(v, depth+1, root); 
            low[u] = min(low[u], low[v]); 
            if (u!=root && low[v]>=dfn[u]) f[u]++; 
            if (u==root && cnt>=2) f[u]++; 
        } else low[u] = min(low[u], dfn[v]); 
    } 
} 
int main() { 
 
    int a, b, l; 
    char s[1000]; 
 
    while (scanf("%d", &n) == 1 && n) { 
        for (int i=0; i<=n; i++) g[i].clear(); 
 
        while (scanf(" %d", &a) == 1 && a) { 
            b = 0; 
            gets(s); 
 
            l = strlen(s); 
            for (int i=0; i<l; i++) { 
                if (s[i] == ' ') { 
                    if (b) { 
                        g[a].push_back(b); 
                        g[b].push_back(a); 
                        b = 0; 
                    } 
                } else b = b*10 + s[i]-'0'; 
            } 
            if (b) { g[a].push_back(b); g[b].push_back(a); } 
 
        } 
 
        memset(f, 0, sizeof(f)); 
        memset(vis, false, sizeof(vis)); 
        dfs(1, 1, 1); 
        int ans = 0; 
        for (int i=1; i<=n; i++) if (f[i] >= 1) ans++; 
        printf("%d\n", ans); 
    } 
 
    return 0; 
} 

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
#define N 103
vector<int> g[N];
int n, low[N], dfn[N], f[N];
bool vis[N];

void dfs(int u, int depth, const int &root) {
    dfn[u] = low[u] = depth;
    vis[u] = true;
    int cnt = 0;
    for (int i=0; i<g[u].size(); i++) {
        int v = g[u][i];
        if (!vis[v]) {
            cnt++;
            dfs(v, depth+1, root);
            low[u] = min(low[u], low[v]);
            if (u!=root && low[v]>=dfn[u]) f[u]++;
            if (u==root && cnt>=2) f[u]++;
        } else low[u] = min(low[u], dfn[v]);
    }
}
int main() {

    int a, b, l;
    char s[1000];

    while (scanf("%d", &n) == 1 && n) {
        for (int i=0; i<=n; i++) g[i].clear();

        while (scanf(" %d", &a) == 1 && a) {
            b = 0;
            gets(s);

            l = strlen(s);
            for (int i=0; i<l; i++) {
                if (s[i] == ' ') {
                    if (b) {
                        g[a].push_back(b);
                        g[b].push_back(a);
                        b = 0;
                    }
                } else b = b*10 + s[i]-'0';
            }
            if (b) { g[a].push_back(b); g[b].push_back(a); }

        }

        memset(f, 0, sizeof(f));
        memset(vis, false, sizeof(vis));
        dfs(1, 1, 1);
        int ans = 0;
        for (int i=1; i<=n; i++) if (f[i] >= 1) ans++;
        printf("%d\n", ans);
    }

    return 0;
}