Codeforces Round #216 C Valera and Elections ( DFS )

題目鏈接: C

題目大意: 給出N(N<=10^5)個結點的樹，樹上某些路是需要維修的

選擇某個結點，從這個結點出發到達1結點的路都會被修復

求這些結點的集合，使得這個集合最小並輸出集合的結點(SPJ)

解題思路: 建立無向邊，從1結點出發開始DFS，沒遍歷的點就遍歷

回溯的時候記錄這段路的第一條需要修復的邊頂點加入集合

若該結點的孩子結點已經被加入集合，則不需要再加入集合

代碼:

#include 
#include 
#include 
#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