URAL 1106. Two Teams

Author: 2015-08-18

ACM

, ,

1. 题目

http://acm.timus.ru/problem.aspx?space=1&num=1106

1106. Two Teams

Time limit: 1.0 second
Memory limit: 64 MB
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 output 
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
Problem Author: Dmitry Filimonenkov
Problem Source: Tetrahedron Team Contest May 2001

2. 思路

现有一组标号为1到N的N个人，每个人都和一个或多个人是朋友，要求把这N个人分成两队，使得每一队的每个人在另外一队都有朋友。

依旧可以使用贪心算法，遍历所有N个人：对于编号为n的人，如果n在第一队中没有朋友，则将n放到第一队，将n的所有朋友放到第二队，并将n的所有朋友标记为在第一队有朋友；如果n在第一队中有朋友,则说明n已经在第二队了。

遍历完成，输出第一队的人即可。

3. 代码

#include <stdio.h>

#define MAX_N 101

typedef unsigned char Friends[MAX_N][MAX_N];

void solveE4f_TwoTeams();
int inputFriends(Friends friends);

int main() {
    solveE4f_TwoTeams();
    return 0;
}

Friends friends;
unsigned char inTeam[MAX_N];
bool hasFriendsInTeam1[MAX_N];
void solveE4f_TwoTeams() {
    int n = inputFriends(friends);
    int team1cnt = 0;

    for (int i = 1; i <= n; ++i) {
        if (!hasFriendsInTeam1[i]) {
            inTeam[i] = 1;
            ++team1cnt;
            for (int j = 1; j <= friends[i][0]; ++j) {
                hasFriendsInTeam1[friends[i][j]] = true;
            }
        }
    }

    printf("%d\n", team1cnt);
    for (int i = 1; i <= n; ++i) {
        if (inTeam[i] == 1)
            printf("%d ", i);
    }
    printf("\n");
}

int inputFriends(Friends friends) {
    int n;
    scanf("%d", &n);

    int friendId, cnt;
    for (int i = 1; i <= n; ++i) {
        cnt = 1;
        scanf("%d", &friendId);
        while (friendId != 0) {
            friends[i][cnt++] = friendId;
            scanf("%d", &friendId);
        }
        friends[i][0] = cnt - 1;
    }

    return n;
}