JZOJ 2126. [GDOI 2003] 테두리 삭제

디렉토리:

제목:

분석:

코드(및 조회):

제목:

제목 보기

분석:

이 제목은 정말 물입니다. 가장 일반적인 방법은 바로 뛰고 수집하는 것입니다. 또한 수론 AC: 우리는 하나의 연결도를 형성하려면 최소 n-1개의 변(n을 포인트로 한다)이 필요하다는 것을 알고 있습니다. 그리고 n을 알고 최대 몇 개의 변을 삭제해야 하는지 알고 있습니다. 즉, m-(n-3-1)m--(n-3-1), 간소화하면 m-n+1m-n+1m입니다.

코드(및 조회):

#include
#include
#include
#include
#include
#include
#define LL long long
using namespace std;
inline LL read() {
    LL d=0,f=1;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){d=d*10+s-'0';s=getchar();}
    return d*f;
}
int f[101];
int find(int x)
{
    return x==f[x]? x:f[x]=find(f[x]);
}
void hb(int x,int y)
{
    int a,b;
    a=find(x);b=find(y);
    f[a]=b;
}
int main()
{    
    int n=read(),m=read();
    for(int i=1;i<=n;i++) f[i]=i;
    int ans=0,a,b;
    for(int i=1;i<=m;i++)
    {
        a=read();b=read();
        if(find(a)==find(b)) continue;
        ans++;
        hb(a,b); 
    }
    printf("%d",m-ans);
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

POJ 2236 Wireless Network 간편한 검색 및 수집

The ACM (Asia Cooperated Medical team) have set up a wireless network with the lap computers, but an unexpected aftersho...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다