Codeforces Round #216 C Valera and Elections ( DFS )

题目链接: C

题目大意: 给出N(N<=10^5)个结点的树，树上某些路是需要维修的

选择某个结点，从这个结点出发到达1结点的路都会被修复

求这些结点的集合，使得这个集合最小并输出集合的结点(SPJ)

解题思路: 建立无向边，从1结点出发开始DFS，没遍历的点就遍历

回溯的时候记录这段路的第一条需要修复的边顶点加入集合

若该结点的孩子结点已经被加入集合，则不需要再加入集合

代码:

#include #include #include #define MAX 101000struct 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