CodeForces 25D - Roads not only in Berland

4141 단어 함께 조사하여 모으다codeforces
이 문제는 문제를 모으는 데 있어서 개인적으로 본 문제의 답안이 유일한 문제가 아니라고 생각하는 것은 두 곳 사이의 의사소통을 편리하게 하기 위해서이다. 따라서 한 길을 삭제할 때 다른 길(하루에 한 번만 할 수 있다)을 소통하고 소요 일수를 최대한 적게 하기 때문에 여기서 순환이 되는지 아닌지를 조사하고 판단해야 한다.성환의 길을 끊은 다음에 단점에서 다른 고리와 교점이 없는 노선을 연결한다. 찌꺼기는 상세하게 말하지 못할 수도 있다. 각 신들은 코드와 제목의 예시를 결합시켜 다시 생각해 보자. 여기까지 말하고 아래에 AC 코드를 첨부한다.
      #include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int pre[1005];
struct Node{
    int u,v;
}a[1005];
int find(int x){
    if(x!=pre[x]){
        pre[x]=find(pre[x]);
    }
    return pre[x];
}
void join(int x,int y){
    int i=find(x);
    int j=find(y);
    pre[i]=j;
}
int main(){
    int n;
    while(~scanf("%d",&n)){
        int cnt=0;
        for(int i=0;i<=n;i++){
            pre[i]=i;
        }
        for(int i=0;i<n-1;i++){
            int x,y;
            scanf("%d %d",&x,&y);
            if(find(x)==find(y)){
                a[cnt].u=x;
                a[cnt].v=y;
                cnt++;
            }
            else{
                join(x,y);
            }
        }
        printf("%d
",cnt);
        int sum=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(find(i)!=find(j)){
                    printf("%d %d %d %d
",a[sum].u,a[sum].v,i,j);
                    join(i,j);
                    sum++;
                    if(sum==cnt) break;
                }
            }
        }
    }
}
[CSS] Layout(display, visibility, float, position, overflow, z-index)
GIT 정보

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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