记录编号 |
321038 |
评测结果 |
AAAAAAAAAA |
题目名称 |
[NOIP 2010冲刺四]晨跑路径 |
最终得分 |
100 |
用户昵称 |
KZNS |
是否通过 |
通过 |
代码语言 |
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