POJ 1308 Is It A Tree? && NYOJ 129 (나무의 판정 + 병 집)
[제목 대의] 여러 쌍 의 노드 를 정 하여 모든 노드 가 한 그루 의 나 무 를 구성 할 수 있 는 지 판단 한다.
[문제 풀이 사고] 그리고 집합 을 찾 는 기본 동작 은 node, edge 를 정의 하고 node 와 edge 의 수 를 통계 합 니 다. 만약 (edge = = node - 1 | node = 0) 이 트 리 가 될 수 있 습 니 다.
나무의 판정: n 개 노드, 최대 n - 1 개의 링, 1 개의 입 도 는 변 이 고 0 이 되 지 않 는 점, 다른 입 도 는 1 보다 크 지 않 습 니 다. 그러나 poj 데이터 에서 만약 에 110 0 이 요구 에 부합 되 지 않 으 면 자신 이 자신 을 가리 키 지 못 하 는 것 을 주의해 야 합 니 다.
코드:
/*
Author:HRW
：
n ， n-1
0
1
*/
//#include <bits/stdc++.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
using namespace std;
const int N=100005;
int father[N],sum[N],a,b,node,edge,vis[N],flag;
int find(int x){if(x==father[x]) return x; return father[x]=find(father[x]); }
void Union(int a,int b){
if(!vis[a]) node++,vis[a]=true;
if(!vis[b]) node++,vis[b]=true;
int pa=find(a);
int pb=find(b);
if(pa!=pb)
{
father[pa]=pb;
edge++;
}
else flag=true;
}
void init(){
node=edge=0;
flag=false;
memset(vis,false,sizeof(vis));
for(int i=1; i<N; i++) father[i]=i;//father
}
int main()
{
int a,b,tot=1;
init();
while(scanf("%d%d",&a,&b)&&a!=-1&&b!=-1){
if(a==0&&b==0){
printf("Case %d %s
",tot++,(!flag&&(edge==node-1||node==0))?"is a tree.":"is not a tree.");
init();
continue;
}
Union(a,b);
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
