【ACM】区间并算法

xiaoxiao2021-02-28  42

#include <iostream> using namespace std; struct Node { int left, right; int father; }node[1000]; bool Judge(int a, int b) { if(node[b].left >= node[a].right || node[b].right <= node[a].left) { return false; } else return true; } void Union(int a, int b) { int af = a; int bf = b; while(node[af].father != af) af = node[af].father; while(node[bf].father != bf) bf = node[bf].father; if(af<bf) node[bf].father = af; else if(af>bf) node[af].father = bf; } int main() { int n; cin>>n; for(int i=0;i<n;i++) { cin>>node[i].left>>node[i].right; node[i].father = i; } for(int i=0;i<n-1;i++) { for(int j=i+1;j<n;j++) { if(Judge(i,j)) { Union(i,j); } } } int sum = 0; for(int i=0;i<n;i++) { if(node[i].father == i) { sum ++; } } printf("sum is %d",sum); return 0; }
转载请注明原文地址: https://www.6miu.com/read-2629580.html

最新回复(0)