1 条题解

  • 0
    @ 2024-12-24 10:06:07

    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
    上传者