rofn123

#include int find(int p[], int x) { //노드가 속한 부분집합의 대표 노드 찾기 if(x==p[x]) return x; return p[x] = find(p, p[x]); } void merge(int p[], int x, int y) {//두개의 노드가 속한 부분집합 합치기 x = find(p, x); y = find(p, y); if(x!=y) p[x] = y; } int same(int p[], int x, int y) {//두 노드의 부분집합은 같은가? x = find(p, x); y = find(p, y); return x==y; } int main(void) { int n, m; scanf("%d %d", &n, &m); //n, m입력 int p[n+1]; //노드..

#include int find(int p[], int x) { //부분집합의 대표 노드 찾기 if(x == p[x]) return x; return p[x] = find(p, p[x]); } void merge(int p[], int x, int y) { //노드가 속한 집합 합치기 x = find(p, x); y = find(p, y); if(x!=y) p[x] = y; return; } int main(void) { int cnt = 0; while(1) { cnt++; int n, m; scanf("%d %d", &n , &m); if(n>0 || m>0) { int p[n+1]; //노드의 부분집합의 대표노드를 담는 곳 int root[n+1][2]; //[0]은 대표노드의 집합의 요소의 개수,..

#include #define M 1000000000 //union find을 이용하면, 특정한 부분집합에 지불할 돈의 최솟값을 구할 수 있으며, //특정한 부분집합들의 최소값을 합친 것이 모든 친구들을 사귈수 있는 돈의 최솟값이 된다!!!!! //특정한 부분집합의 지불할 돈의 최솟값을 구하기 위해서는 그냥, 각각의 사람들의 대표노드를 구하고, 그 대표 사람을 사기(?)위한 돈의 최솟값을 구하면 된다. int find(int p[], int x) { //노드가 속한 부분집합의 대표노드 구하기 if(p[x] == x) return x; return p[x] = find(p, p[x]); } void merge(int p[], int x, int y) { //두개의 노드의 부분집합을 합치기 x = find(..

#include #include int find(int p[], int x) { //노드가 속한 부분집합의 대표 노드를 찾는 함수 if(p[x] == x) return x; return p[x] = find(p, p[x]); } void merge(int p[], int x, int y) {//두개의 노드의 부분집합을 합치는 함수 x = find(p, x); y = find(p, y); if(x!=y) p[x] = y; //p[y] = x 도 상관없습니다. return; } int same(int p[], int x, int y) { //두개의 노드가 같은 부분집합인지를 찾는 함수 x = find(p, x); y = find(p, y); return x==y; } int main(void) { int n..

#include #include int find(int parent[], int x) { if(parent[x] == x) return x; return parent[x] = find(parent, parent[x]); } void merge(int parent[], int x, int y) { x = find(parent, x); y = find(parent, y); if(x != y) parent[x] = y; return; } int same(int parent[], int x, int y) { x = find(parent, x); y = find(parent, y); return x == y; } int main(void) { int n, m; scanf("%d", &n); scanf("%d", ..

#include #include int find(int parent[], int x) { //노드가 속한 부분집합의 대표노드 찾기 if(parent[x] == x) return x; //자기자신이면 자기자신을 리턴 return parent[x] = find(parent, parent[x]); //자기자신이 아니면, 부분집합의 대표노드의 대표노드 찾기 } void merge(int parent[], int x, int y) { //두개의 노드가 속한 집합 합치기 x = find(parent, x); //x의 대표 노드//사실 노드를 합치면 알아서 그 두개의 집합이 연결된다. y = find(parent, y); //y의 대표노드 if(x==y); //같은 노드이면 이미 같은 집합이다. else parent..