#207 Div.2 B. Flag Day

http://codeforces.com/contest/357/problem/B

题目是要将n个数分成三类：有m组输入，每组输入为(a,b,c)，表示a,b,c中任意两个不能出现在同一类中，输出任一可能的分类结果。

这道题和食物链很类似，唯一的区别是食物链的输入是给出两个元素的关系，这个是三个元素，那么可以把(a,b,c)分成(a,b)和(b,c)，用并查集维护当前元素和根元素的关系（需要路径压缩）。

# include <iostream>

const int maxn = 100005;

int n, m;
int x, y, z;
int p[maxn];
int k[maxn];

void make_set(void)
{
    for (int i = 1; i <= n; ++i) 
    {
        p[i] = i;
        k[i] = 0;
    }
}

int find(int e)
{
    if (p[e] != e) 
    {
        int t = p[e];
        p[e] = find(p[e]);
        k[e] = (k[e]+k[t]) % 3;
    }
    return p[e];
}

void join(int a, int b)
{
    int pa = find(a);
    int pb = find(b);
    p[pb] = pa;
    k[pb] = (k[a]+1-k[b]+9)%3; // r(pa, a) r(pb, b) r(a, b) => r(pa, pb)
}

void solve(void)
{
    for (int i = 1; i <= n; ++i)
    {
        find(i);
        std::cout << k[i]+1 << ' ';
    }
    std::cout << std::endl;
}

int main()
{
    std::cin >> n >> m;
    make_set();
    for (int i = 0; i < m; ++i)
    {
        std::cin >> x >> y >> z;
        join(x, y);
        join(y, z);
    }
    solve();

    return 0;
}