1 条题解
-
0
C++ :
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define N 10 struct edge { int v, next, num; } E[N*2]; int n, m, p[N], Ind, deep[N], ancestor[N], mark[N], c[N*2], tn; int dfs(int s, int e, int fnum, int d) { mark[s] = 1; deep[s] = ancestor[s] = d; int z = 0; int ok = 0, tmp; if (s == e) ok = 1; for (int i = p[s]; i != -1; i = E[i].next) { if (E[i].num == fnum) continue; tmp = 0; if (mark[E[i].v]) ancestor[s] = min(ancestor[s], deep[E[i].v]); else { tmp = dfs(E[i].v, e, E[i].num, d + 1); ancestor[s] = min(ancestor[s], ancestor[E[i].v]); z++; if (tmp) { if (ancestor[E[i].v] > deep[s]) c[tn++] = E[i].num; ok = 1; } } } return ok; } int main() { int a, b, i, s, e; while (scanf("%d%d", &n, &m) != EOF) { memset(p, -1, sizeof(p)); Ind = 0; for (i = 0; i < m; i++) { scanf("%d%d", &a, &b); E[Ind].v = b; E[Ind].num = i; E[Ind].next = p[a]; p[a] = Ind++; E[Ind].v = a; E[Ind].num = i; E[Ind].next = p[b]; p[b] = Ind++; } scanf("%d%d", &s, &e); tn = 0; memset(mark, 0, sizeof(mark)); dfs(s, e, -1, 1); sort(c, c + tn); printf("%d\n", tn); for (i = 0; i < tn; i++) printf(i == tn - 1 ? "%d\n" : "%d ", c[i]); } return 0; }
- 1
信息
- ID
- 1952
- 时间
- 1000ms
- 内存
- 32MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者