백준 2617번 - 구슬찾기 소스 코드

https://www.acmicpc.net/problem/2617

2617번: 구슬 찾기

 

[ 한국정보올림피아드 2003년 중등부 구슬찾기 소스 코드 ]

#include <stdio.h>
int a[200][200], b[200][200], c[200], d[200], e[200], f[200];
int aa[200][200], n, m, cnt, dab,cnt2;
void sub(int x){
	int i;
	for(i=0;i<c[x];i++){
		if(e[a[x][i]]==0){
			e[a[x][i]]=1; 
			cnt++; 
			sub(a[x][i]);
		}
	}
}
void sub2(int x){
	int i;
	for(i=0;i<d[x];i++){
		if(f[b[x][i]]==0){
			f[b[x][i]]=1; 
			cnt2++; 
			sub2(b[x][i]);
		}
	}
}
int main()
{
	int i, j, x, y;

	scanf( "%d %d", &n, &m);
	
	for(i=0;i<m;i++)
	{
		scanf("%d %d", &x, &y);
		if(aa[x][y]==0){
			a[x][c[x]++]=y; 
			b[y][d[y]++]=x; 
			aa[x][y]=1;
		}
	}
	for(i=1;i<=n;i++){
		e[i]=1; 
		cnt=0; 
		sub(i);

		f[i]=1; 
		cnt2=0; 
		sub2(i);

		if(cnt > n/2 || cnt2>n/2)
			dab++;
		
		for(j=1;j<=n;j++){
			e[j]=0; 
			f[j]=0;
		}
	}
	printf("%d", dab);
	return 0;
}