/* -*- c++ -*-
   ID: dirtysalt
   PROG: 
   LANG: C++
   copy[write] by dirlt(dirtysalt1987@gmail.com) */
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <cassert>
#include <cstring>

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <numeric>
#include <algorithm>

using namespace std;
typedef long long LL;
typedef vector < int >VI;
typedef vector < string > VS;
typedef vector < double >VD;
typedef pair < int, int >PII;
#define SZ(v) ((int)((sizeof(v))/sizeof(*(v))))

#define MAX_N 1010
#define MAX_DEG 4
#define MAX_M (MAX_DEG*MAX_N/2)

int n, m;
int deg[MAX_N + 1];
int adj[MAX_N + 1][MAX_DEG];
int dfs[MAX_N + 1];
int back[MAX_N + 1];
int n_stack, dfn;
int v_stack[MAX_M];
int w_stack[MAX_M];

int
min(int x, int y)
{
    return (x < y) ? x : y;
}

int
read_case(void)
{
    int i, u, v, t;

    t = scanf("%d %d", &n, &m);
    if (n == 0 && m == 0) {
        return 0;
    }

    for (i = 1; i <= n; i++) {
        deg[i] = 0;
    }
    for (i = 0; i < m; i++) {
        t = scanf("%d %d", &u, &v);
        adj[u][deg[u]++] = v;
        adj[v][deg[v]++] = u;
    }
    return 1;
}

void
bicomp(int v, int pred)
{
    int i, w, count;

    dfn++;
    dfs[v] = back[v] = dfn;
    for (i = 0; i < deg[v]; i++) {
        w = adj[v][i];
        if (dfs[w] < dfs[v] && w != pred) {
            /* back edge or unexamined forward edge */
            v_stack[n_stack] = v;
            w_stack[n_stack] = w;
            n_stack++;
        }
        if (!dfs[w]) {
            bicomp(w, v);
            /* back up from recursion */
            if (back[w] >= dfs[v]) {
                /* new bicomponent */
                count = 0;
                while (v_stack[n_stack - 1] != v || w_stack[n_stack - 1] != w) {
                    //assert(n_stack > 0);
                    printf("%d %d\n", v_stack[n_stack - 1],
                           w_stack[n_stack - 1]);
                    n_stack--;
                    count++;
                }
                printf("%d %d\n", v_stack[n_stack - 1], w_stack[n_stack - 1]);
                if (count == 0) {
                    /* we have a bicomponent containing only one edge */
                    printf("%d %d\n", w_stack[n_stack - 1],
                           v_stack[n_stack - 1]);
                }
                n_stack--;
            } else {
                back[v] = min(back[v], back[w]);
            }
        } else {
            /* w has been examined already */
            back[v] = min(back[v], dfs[w]);
        }
    }
}

void
do_case(void)
{
    int i;

    n_stack = 0;
    dfn = 0;
    for (i = 1; i <= n; i++) {
        dfs[i] = 0;
    }
    bicomp(1, -1);
}

int
main(void)
{
    int case_no = 1;
    while (read_case()) {
        printf("%d\n\n", case_no++);
        do_case();
        printf("#\n");
    }
    return 0;
}

• Re:人气这么低,贴个标程作参考. (2) qinpxi 2010-11-23 16:11:23