Posted on 2007-02-12 02:47
魔のkyo 阅读(182)
评论(0) 编辑 收藏 引用
//
2007-02-12 02:13:52 Accepted 1789 C++ 00:00.04 2988K
//
一次AC
//
算法:分支限界法(用队列搜)
#include
<
iostream
>
#include
<
vector
>
#include
<
queue
>
#include
<
numeric
>
using
namespace
std;
typedef vector
<
int
>
vector_int;
int
main ()
{
int
n,m;
while
(scanf(
"
%d %d
"
,
&
n,
&
m)
!=
EOF
&&
(n
||
m)){
int
marked_person[
30000
]
=
{
1
},marked_group[
500
]
=
{
0
};
//
标记有嫌疑的人,和有嫌疑的组
queue
<
int
>
Q;
//
用来BFS有嫌疑的组
vector_int
*
vGroup
=
new
vector_int [m];
vector_int
*
vPerson
=
new
vector_int [n];
for
(
int
i
=
0
;i
<
m;i
++
){
int
k,t;
scanf(
"
%d
"
,
&
k);
for
(
int
j
=
0
;j
<
k;j
++
){
scanf(
"
%d
"
,
&
t);
vGroup[i].push_back(t);
//
Group i中有t这个成员
vPerson[t].push_back(i);
//
Person t参加了i这个组
if
(
!
t){
marked_group[i];
//
标记所有包含0这个成员的Group
Q.push(i);
//
有嫌疑的组入队
}
}
}
while
(
!
Q.empty()){
int
tempQNode
=
Q.front();
//
取出一个嫌疑组
Q.pop();
for
(
int
i
=
0
;i
<
vGroup[tempQNode].size();i
++
){
//
遍历嫌疑组中的所有人
int
tempPerson
=
vGroup[tempQNode][i];
if
(
!
marked_person[tempPerson]){
//
如果这个人没有被标记过
marked_person[tempPerson]
=
1
;
//
标记嫌疑人
for
(
int
j
=
0
;j
<
vPerson[tempPerson].size();j
++
){
//
遍历这个人所加入的所有组
int
tempGroup
=
vPerson[tempPerson][j];
if
(
!
marked_group[tempGroup]){
//
如果嫌疑人加入的组没有被标记过
marked_group[tempGroup]
=
1
;
//
标记嫌疑组
Q.push(tempGroup);
//
嫌疑组入队
}
}
}
}
}
printf(
"
%d\n
"
,accumulate(marked_person,marked_person
+
n,
0
));
delete [] vGroup;
delete [] vPerson;
}
}