题目链接:
C
题目大意: 给出N(N<=10^5)个结点的树,树上某些路是需要维修的
选择某个结点,从这个结点出发到达1结点的路都会被修复
求这些结点的集合,使得这个集合最小并输出集合的结点(SPJ)
解题思路: 建立无向边,从1结点出发开始DFS,没遍历的点就遍历
回溯的时候记录这段路的第一条需要修复的边顶点加入集合
若该结点的孩子结点已经被加入集合,则不需要再加入集合
代码:
#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 101000 struct snode{ int to,w,next; }Tree[MAX<<2]; int visit[MAX],pre[MAX],sum[MAX],Index,Answer[MAX],Ansn; void Add_edge(int a,int b,int c) { Tree[Index].w=c;Tree[Index].to=b; Tree[Index].next=pre[a]; pre[a]=Index++; } int DFS(int Star,int w) { visit[Star]=1; //记录结点被访问过 int i,v,pd=0,kk=0; for(i=pre[Star];i!=-1;i=Tree[i].next) { if(visit[Tree[i].to]) continue; sum[Star]+=DFS(Tree[i].to,Tree[i].w); } if(w==2||sum[Star]>=1) //若该条路需要被修复||子节点已经被修复 { if(sum[Star]==0) //未被记录则加入集合 { Answer[Ansn++]=Star; } return 1; } else //不需要修复 return 0; } int main() { int n,i,j,a,b,c,ans; while(scanf("%d",&n)!=EOF) { Index=ans=Ansn=0; memset(pre,-1,sizeof(pre)); memset(sum,0,sizeof(sum)); memset(visit,0,sizeof(visit)); for(i=1;i<n;i++) { scanf("%d%d%d",&a,&b,&c); Add_edge(a,b,c); Add_edge(b,a,c); } visit[1]=1; ans+=DFS(1,0); //1结点开始深搜 printf("%d\n",Ansn); for(i=0;i<Ansn;i++) { printf("%d",Answer[i]); if(i!=Ansn) printf(" "); } puts(""); } return 0; }