kickstart-2018-f-b.cpp

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define INF INT_MAX
#define NINF INT_MIN
#define MAX 55

typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef unordered_map<int, vector<pii>> gmap;
typedef unordered_map<int, int> umap;

vector<pair<int, pii>> edges;
int v, e;
set<int> zero;
set<int> vis;

void init(){
    edges.clear();
    zero.clear();
}

void addEdge(int x, int y, int w){
    if(w==0){
        zero.insert(x);
        zero.insert(y);
    }
    edges.pb(mp(w, mp(x, y)));
}

bool isVisit(int x){
    return vis.find(x)!=vis.end();
}

bool isZero(int x){
    return zero.find(x)!=zero.end();
}

ll solve(){
    vis.clear();
    sort(edges.begin(), edges.end());
    int x, y;
    ll result = 1;
    for(int i=0; i<e; i++){
        x = edges[i].S.F;
        y = edges[i].S.S;
        if(!isVisit(x) && !isVisit(y)){
            result*=2;
            vis.insert(x);
            vis.insert(y);
        }else if((!isVisit(x) && isVisit(y)) || (isVisit(x) && !isVisit(y))){
            if(isZero(x) || isZero(y)) result*=2;
            vis.insert(x);
            vis.insert(y);
        }
    }
    return result;
}

int main(){
    int t;
    cin>>t;
    int x, y, z;
    for(int i=1; i<=t; i++){
        cin>>v>>e;
        init();
        for(int j=0; j<e; j++){
            cin>>x>>y>>z;
            addEdge(x, y, z);
        }
        cout<<"Case #"<<i<<": "<<solve()<<endl;;
    }
}