记录编号 321038 评测结果 AAAAAAAAAA
题目名称 [NOIP 2010冲刺四]晨跑路径 最终得分 100
用户昵称 GravatarKZNS 是否通过 通过
代码语言 C++ 运行时间 0.011 s
提交时间 2016-10-13 08:20:43 内存使用 0.35 MiB
显示代码纯文本
//KZNS
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define Nmax 2003
int N, M;
vector<int> gp[Nmax];
vector<int> als;
void init() {
    scanf("%d %d", &N, &M);
    int a, b;
    for (int i = 0; i < M; i++) {
        scanf("%d %d", &a, &b);
        gp[a].push_back(b);
        gp[b].push_back(a);
    }
}
int dtm[Nmax] = {0};
int low[Nmax] = {0};
bool hvn[Nmax] = {false};
int ttmm = 1;
void tarjan(int x, int f) {
    low[x] = dtm[x] = ttmm++;
    int t;
    bool cbg = false;
    for (int i = 0; i < gp[x].size(); i++) {
        if ((t = gp[x][i]) == f)
            continue;
        if (dtm[t])
            low[x] = min(low[x], dtm[t]);
        else {
            tarjan(t, x);
            low[x] = min(low[x], low[t]);
            if (low[t] >= dtm[x] && hvn[t])
                cbg = true;
            if (hvn[t])
                hvn[x] = true;
        }
    }
    if (cbg)
        als.push_back(x);
    if (x == N)
        hvn[x] = true;
}
int main() {
    freopen("running.in", "r", stdin);
    freopen("running.out", "w", stdout);
    init();
    tarjan(1, 0);
    sort(als.begin(), als.end());
    printf("%d\n", als.size()-1);
    for (int i = 1; i < als.size(); i++)
        printf("%d ", als[i]);
    return 0;
}
//UBWH