Submission #3680

#	Time	Username	Problem	Language	Result	Execution time	Memory
3680		pl0892029	Cactus? Not cactus? (kriii1_C)	C++98	0 / 1	0 ms	1868 KiB

C

#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 / 1