Submission #3598

#	Time	Username	Problem	Language	Result	Execution time	Memory
3598		movie_jo	Cactus? Not cactus? (kriii1_C)	C11	0 / 1	28 ms	2260 KiB

C

#include <stdio.h>

int x[100001];
int group[100001], gl = 1;
int cycle[100001];
int main(void)
{
	int N, M, i, a, b, y, z, chk = 0;

	scanf("%d %d", &N, &M);

	for(i = 0; i < M; i++)
	{
		scanf("%d %d", &a, &b);

		if(chk)
			continue;

		if(x[a])
		{
			if(x[b])
			{
				y = x[a];
				z = x[b];

				while(group[y] != y)
					y = group[y];

				while(group[z] != z)
					z = group[z];

				if(y == z)
				{
					cycle[y]++;

					if(cycle[y] > 1)
						chk = 1;
				}
				else
				{
					if(y > z)
					{
						group[y] = z;
						group[x[a]] = z;
					}
					else
					{
						group[z] = y;
						group[x[b]] = y;
					}
				}

			}
			else
			{
				x[b] = x[a];
			}
		}
		else if(x[b])
		{
			x[a] = x[b];
		}
		else
		{
			x[a] = gl;
			x[b] = gl;
			group[gl] = gl;
			gl++;
		}
	}

	printf("%sactus\n", chk?"Not c":"C");

	return 0;
}

• Subtask 1: 0 / 1