记录编号	42891	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺四]晨跑路径	最终得分	100
用户昵称	codewaysky	是否通过	通过
代码语言	C++	运行时间	0.029 s
提交时间	2012-10-02 00:27:08	内存使用	0.36 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

const int kMaxN = 2000 + 10;

int n, m;
vector<int> graph[kMaxN];

int tarjan_root;
int tarjan_count;
int tarjan_dfn[kMaxN];
int tarjan_low[kMaxN];
stack<int> tarjan_stack;
bool tarjan_instack[kMaxN];
int cut_vertex[kMaxN];

void Tarjan(int v, int from) {
    tarjan_count++;
    tarjan_dfn[v] = tarjan_count;
    tarjan_low[v] = tarjan_count;
    tarjan_instack[v] = true;
    tarjan_stack.push(v);

    for (int i = 0; i < (int)graph[v].size(); i++) {
        int w = graph[v][i];
        if (w == from) continue;
        if (!tarjan_dfn[w]) {
            Tarjan(w, v);
            tarjan_low[v] = min(tarjan_low[v], tarjan_low[w]);

            if (tarjan_dfn[v] <= tarjan_low[w]) {
                if (v == tarjan_root) {
                    if ((int)graph[v].size() >= 2 && tarjan_dfn[v] < tarjan_low[w]) {
                        cut_vertex[v] = true;
                    }
                } else {
                    cut_vertex[v] = true;
                }
            }
        } else if (tarjan_instack[w]) {
            tarjan_low[v] = min(tarjan_low[v], tarjan_dfn[w]);
        }
    }

    if (tarjan_dfn[v] == tarjan_low[v]) {
        int t;
        do {
            t = tarjan_stack.top();
            tarjan_stack.pop();
            tarjan_instack[t] = false;
        } while (t != v);
    }
}

bool used[kMaxN];

bool Dfs(int v, int s) {
    if (v == n) {
        return true;
    }

    used[v] = true;
    for (int i = 0; i < (int)graph[v].size(); i++) {
        int w = graph[v][i];
        if (!used[w] && w != s) {
            if (Dfs(w, s)) {
                return true;
            }
        }
    }
    return false;
}

void Work() {
    tarjan_count = 0;
    for (int i = 1; i <= n; i++) {
        if (!tarjan_dfn[i]) {
            tarjan_root = i;
            Tarjan(i, -1);
        }
    }

    int cut_sum = 0;
    for (int i = 2; i < n; i++) {
        if (cut_vertex[i]) {
            memset(used, false, sizeof(used));
            if (Dfs(1, i)) {
                cut_vertex[i] = false;
            } else {
                cut_sum++;
            }
        }
    }

    printf("%d\n", cut_sum);
    for (int i = 2; i < n; i++) {
        if (cut_vertex[i]) {
            printf("%d ", i);
        }
    }
    printf("\n");
}

int main() {
    freopen("running.in", "r", stdin);
    freopen("running.out", "w", stdout);

    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    Work();

    return 0;
}