Codeforces Round #600(Div.2) D 문항
21448 단어 #codeforces 상분 기록함께 조사하여 모으다
You’re given an undirected graph with n nodes and m edges. Nodes are numbered from 1 to n.
The graph is considered harmonious if and only if the following property holds:
For every triple of integers (l,m,r) such that 1≤l In other words, in a harmonious graph, if from a node l we can reach a node r through edges (l
What is the minimum number of edges we need to add to make the graph harmonious?
Input The first line contains two integers n and m (3≤n≤200 000 and 1≤m≤200 000).
The i-th of the next m lines contains two integers ui and vi (1≤ui,vi≤n, ui≠vi), that mean that there’s an edge between nodes u and v.
It is guaranteed that the given graph is simple (there is no self-loop, and there is at most one edge between every pair of nodes).
Output Print the minimum number of edges we have to add to the graph to make it harmonious.
그리고 수집+사유;
각 집합의 최대 최소치 사이의 값을 매거하고 아버지가 같지 않으면 연결하고 변수에 1을 더한다.
#include
#define LL long long
#define pa pair
#define lson k<<1
#define rson k<<1|1
#define inf 0x3f3f3f3f
//ios::sync_with_stdio(false);
using namespace std;
const int N=200100;
const int M=200100;
const LL mod=998244353;
int n,m;
int fa[N];
int find(int p){
if(p==fa[p]) return p;
return fa[p]=find(fa[p]);
}
int vis[N];
struct Node{
int mmin,mmax;
}bin[N];
bool cmp(Node p,Node q){
return p.mmin<q.mmin;
}
bool d[N];
int main(){
// ios::sync_with_stdio(false);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
bin[i].mmax=0;
bin[i].mmin=2e9;
fa[i]=i;
}
int u,v;
int ans=0;//
for(int i=1;i<=m;i++){
scanf("%d%d",&u,&v);
if(!vis[u]&&!vis[v]){
ans++;
vis[u]=vis[v]=ans;
}
else if(vis[u]||vis[v]){
if(vis[u]) vis[v]=vis[u];
else vis[u]=vis[v];
}
if(u>v){
fa[find(v)]=find(fa[u]);
bin[vis[u]].mmax=bin[vis[u]].mmax>u?bin[vis[u]].mmax:u;
bin[vis[u]].mmin=bin[vis[u]].mmin<v?bin[vis[u]].mmin:v;
}
else{
fa[find(u)]=find(fa[v]);
bin[vis[u]].mmax=bin[vis[u]].mmax>v?bin[vis[u]].mmax:v;
bin[vis[u]].mmin=bin[vis[u]].mmin<u?bin[vis[u]].mmin:u;
}
}
sort(bin+1,bin+1+ans,cmp);
int sum=0;
int last=0;
for(int i=1;i<=ans;i++){
int f=find(bin[i].mmin);//
last=max(last,bin[i].mmin);
for(int j=last;j<bin[i].mmax;j++){
if(d[j]) continue;//
d[j]=true;
if(find(fa[j])!=f){
if(fa[j]==j){//
fa[j]=f;
sum++;
}
else{
if(fa[j]>f){//
fa[find(f)]=find(fa[j]);
f=find(fa[j]);
}
else{
fa[find(fa[j])]=find(f);
}
sum++;
}
}
}
last=bin[i].mmax;
}
printf("%d
",sum);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Rails Turbolinks를 페이지 단위로 비활성화하는 방법원래 Turobolinks란? Turbolinks는 링크를 생성하는 요소인 a 요소의 클릭을 후크로 하고, 이동한 페이지를 Ajax에서 가져옵니다. 그 후, 취득 페이지의 데이터가 천이 전의 페이지와 동일한 것이 있...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.