E – Two Teams

E -Two TeamsTime Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64uSubmitStatus Practice URAL 1106
Description
The group of people consists of N members. Every member has one or more friends in the group. You are to write program that divides this group into two teams. Every member of each team must have friends in another team.
Input
The first line of input contains the only number N (N ≤ 100). Members are numbered from 1 to N. The second, the third,…and the (N+1)th line contain list of friends of the first, the second, …and the Nth member respectively. This list is finished by zero. Remember that friendship is always mutual in this group.
Output
The first line of output should contain the number of people in the first team or zero if it is impossible to divide people into two teams. If the solution exists you should write the list of the first group into the second line of output. Numbers should be divided by single space. If there are more than one solution you may find any of them.
Sample Input

7
2 3 0
3 1 0
1 2 4 5 0
3 0
3 0
7 0
6 0

4
2 4 5 6

题意大意：

给出N人，以下N行表示所交朋友，0结束

把这些人划分为两个team，team成员必须至少有一个朋友在另一个team

题解：

每个人有两个标记量，记录是否有朋友在teamA，在teamB；

从头检索

若teamA为false，则把自己放到teamA，标记朋友圈的teamA为true，表示有朋友在teamA

否则

若teamB为false，把自己放到teamB，标记朋友圈的teamB为true，表示有朋友在teamB

否则

说明teamA和teamB都为true，则该人放在teamA或teamB都可以，可不做处理

1 //
 2 /*
 3 
 4 */
 5 #include <cstdio>
 6 
 7 
 8 #define N 101
 9 
10 bool flag[N][2];
11 int fri[N][N];
12 int ans [N];
13 int ansc;
14 
15 int main()
16 {
17     int n;
18     while(scanf("%d",&n)!=EOF)
19     {
20         ansc = 0;
21         for (int i=0;i<n;i++)
22         {
23             ans[i] = 0;
24             flag[i][0] = false;
25             flag[i][1] = false;
26             int j=0;
27             do
28             {
29                 scanf("%d",&fri[i][j]);
30                 fri[i][j]--;
31             }while(fri[i][j++]!=-1);
32         }
33         ans[n] = 0;
34         for (int i=0;i<n;i++)
35         {
36             if (flag[i][0]==false)
37             {
38                 ans[ansc++] = i+1;
39                 int j=0;
40                 do
41                 {
42                     flag[fri[i][j]][0] = true;
43                 }while(fri[i][j++]!=-1);
44             } else
45             {
46                 if (flag[i][1]==false)
47                 {
48                     int j=0;
49                     do
50                     {
51                         flag[fri[i][j]][1] = true;
52                     }while(fri[i][j++]!=-1);
53                 }
54             }
55         }
56         printf("%d\n%d",ansc,ans[0]);
57         for (int i=1;i<ansc;i++)
58         {
59             printf(" %d",ans[i]);
60         }
61         printf("\n");
62     }
63     return 0;
64 }

By fenrir1205

原文链接: https://www.cnblogs.com/scnuacm/p/3201718.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍