oj.uz

답안 #3680

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
3680 2013-08-31T07:39:13 Z pl0892029 Cactus? Not cactus? (kriii1_C) C++
0 / 1
 0 ms 1868 KB 
#include <cstdio>

int groupNumber[100001];
int groupCount[100001];

bool isSameSet(int a,int b) {
 return groupNumber[a] == groupNumber[b];
}

void setUnion(int a,int b) {
 if( groupCount[a] < groupCount[b] ) {
  groupCount[b] += groupCount[a];
  groupCount[a] = 0;
  groupNumber[a] = b;
 }
 else {
  groupCount[a] += groupCount[a];
  groupCount[b] = 0;
  groupNumber[b] = a;
 }
}

int setFind(int n) {
 if( groupCount[n] == 0 ) {
  groupNumber[n] = setFind(groupNumber[n]);
 }
 return groupNumber[n];
}

int main() {
 int n, m;
 scanf("%d %d",&n,&m);

 for(int i=1;i<=n;i++) {
  groupCount[i] = 1;
  groupNumber[i] = i;
 }

 int count = 0;

 for(int i=0;i<m;i++) {
  int a, b;
  scanf("%d %d",&a,&b);
  int u = setFind(a);
  int v = setFind(b);

  if( isSameSet(u,v) ) {
   printf("add count\n");
   count++;
  }
  else
   setUnion(u,v);
 }
 if( count > 1 )
  printf("Not cactus");
 else
  printf("Cactus");
}

Subtask #1
0.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 1868 KB Output isn't correct
2 Halted 0 ms 0 KB -