Friends
Problem's Link: http://acm.hdu.edu.cn/showproblem.php?pid=5305
Mean:
n个人,m对朋友关系,每个人的朋友中又分为在线好友和不在线好友,对于每个人都要保证在线好友和不在线好友一样多,求方案数有多少种。
analyse:
我们用m对关系建立一个无向图(存边即可),同时统计每个节点的度。
首先可以确定的是:如果某个节点的度是奇数,很显然answer=0。
将每个节点的度分为两组:online和offonline。
初始时,每个节点的online和offonline是相等的。
然后就是dfs统计答案。
如何统计呢?
dfs统计答案的实质就是枚举每一条边的两种属性(online和offonline).
如果枚举得到的状态能满足条件,在程序中可以走到m+1状态,此时是一种答案,ans++。
在dfs时,我们把每条边对应的两个节点的online值同增同减,且回溯时将减掉的online加回来,这样就保证了online和offonline在相同数量的边的情况下是相等的。
这种做法还是很巧妙的。
Time complexity: O(N)
Source code:
)
);
);
);
;
; ; ;
)
);
;
}
/*
);
);
);
;
; ; ;
)
);
;
}
/*
*/