2015年2月16日 星期一

2015/02/16 Codeforces 505B. Mr. Kitayuta's Colorful Graph

/*
    DSU (Disjoint Set Union)
*/
// http://codeforces.com/problemset/problem/505/B
#include <iostream>
#include <cstdio>

using namespace std;

int N, M, Q;
int par[20000];

int anc(int x)
{
    return x == par[x] ? x : par[x] = anc(par[x] );
}

void combine(int x, int y)
{
    int px = anc(x);
    int py = anc(y);
    par[px] = py;
}

int main()
{
    scanf("%d %d", &N, &M);

    for(int Mi = 1; Mi <= M; Mi++)
        for(int Ni = 1; Ni <= N; Ni++)
        {
            int p = (Mi-1)*N+Ni;
            par[p] = p;
        }

    for(int Mi = 1; Mi <= M; Mi++)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);

        a = (c-1)*N+a;
        b = (c-1)*N+b;
        combine(a, b);
    }

    scanf("%d", &Q);

    for(int Qi = 1; Qi <= Q; Qi++)
    {
        int u, v;
        scanf("%d %d", &u, &v);

        int Ans = 0;

        for(int Mi = 1; Mi <= M; Mi++)
        {
            int a, b;
            a = (Mi-1)*N+u;
            b = (Mi-1)*N+v;

            if( anc(a) == anc(b) ) Ans++;
        }

        printf("%d\n", Ans);
    }
}

沒有留言:

張貼留言