Codeforce 219D

링크:클릭하여 링크 열기
제목: n 각 노드로 구성된 유방향 나무는 한 점을 수도로 선택하고 반전을 통해 어느 한 점이 수도에 도달할 수 있도록 한다. 반전의 최소 횟수와 수도가 될 수 있는 노드 번호를 출력한다.
코드:

#include <vector>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int SIZE=200005;
const int INF=0x3f3f3f3f;
int dp[SIZE],num[SIZE],used[SIZE];
struct node{
    int to,cost;
};
vector<node> G[SIZE];
void dfs1(int s,int sum){
    int i,tmp;
    dp[1]+=sum;
    used[s]=1;
    for(i=0;i<G[s].size();i++){
        tmp=G[s][i].to;
        if(G[tmp].size()&&!used[tmp]){
        dfs1(tmp,G[s][i].cost);
        }
    }
}                                               // 1    ，           
void dfs2(int s){                               //             
    int i,tmp;
    used[s]=1;
    for(i=0;i<G[s].size();i++){
        tmp=G[s][i].to;
        if(!used[tmp]){
            if(G[s][i].cost==0)                 //          
            dp[tmp]=dp[s]+1;
            else
            dp[tmp]=dp[s]-1;
            dfs2(tmp);
        }
    }
}
int main(){                                     //        1，     0
    int n,i,j,a,b,ans;                          //               
    while(scanf("%d",&n)!=EOF){
        ans=INF;
        for(i=1;i<=n;i++)
        G[i].clear();
        memset(dp,0,sizeof(dp));
        memset(used,0,sizeof(used));
        for(i=0;i<n-1;i++){
            scanf("%d%d",&a,&b);
            G[b].push_back((node){a,1});
            G[a].push_back((node){b,0});
        }                                       //  
        dfs1(1,0);
        memset(used,0,sizeof(used));
        dfs2(1);
        for(i=1;i<=n;i++)
        ans=min(ans,dp[i]);                     //     
        printf("%d
",ans);
        for(i=1;i<=n;i++)
        if(dp[i]==ans)
        printf("%d ",i);
        printf("
");
    }
    return 0;
}