Proficient.
Put your skills to the test.

Problem summary

Choose roads forming a spanning tree of a connected undirected graph while minimizing how many chosen roads are difficult. Roads have difficulty zero or one.

Constraints

2 ≤ N ≤ 50000; 1 ≤ M ≤ 100000; d is 0 or 1; the graph is connected and has no parallel roads.

Worked example

An independently prepared example for this explanation.

9 12
1 2 0
2 3 0
4 5 1
5 6 1
4 8 0
8 9 0
1 4 0
4 7 0
2 5 1
5 8 1
3 6 0
6 9 0

1

Solution analysis

1. Keep only easy roads and find their connected components using disjoint set union. Within any such component, a spanning tree can be built using only easy roads.
2. If there are C easy-road components, at least C−1 difficult roads are needed to join them. Contracting those components leaves a connected graph because the original graph is connected, so C−1 difficult roads also suffice.
3. In the sample, city 5 is separated from the large component when difficult roads are removed. Thus there are two components, and one difficult road connecting city 5 to the rest is sufficient.

Why it works

Every road crossing distinct easy-road components must be difficult. A connected network on C components needs at least C−1 crossing edges. The contracted graph is connected, so it has a spanning tree of C−1 such edges; combining it with easy spanning trees inside each component gives a spanning tree achieving the bound.

Watch out. Ignore difficult roads only while forming the easy components, and rely on the guaranteed connectivity of the complete graph. Return components−1, not the number of isolated cities.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<numeric>
#include<algorithm>
// Algorithm: Keep only easy roads and find their connected components using disjoint set union.
using namespace std;
struct DisjointSet{
    vector<int>parent,size;
    explicit DisjointSet(int n):parent(n+1),size(n+1,1){
        iota(parent.begin(),parent.end(),0);
    }
    int find(int vertex){
        while(parent[vertex]!=vertex){
            parent[vertex]=parent[parent[vertex]];
            vertex=parent[vertex];
        }
        return vertex;
    }
    bool join(int first,int second){
        first=find(first);
        second=find(second);
        if(first==second){
            return false;
        }
        if(size[first]<size[second]){
            swap(first,second);
        }
        parent[second]=first;
        size[first]+=size[second];
        return true;
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    DisjointSet components(n);
    int count=n;
    for(int i=0;i<m;++i){
        int first,second,difficulty;
        cin>>first>>second>>difficulty;
        if(difficulty==0&&components.join(first,second)){
            --count;
        }
    }
    cout<<count-1<<'\n';
}