글 읽기 - 구슬찾기문제 시간초과 ㅜㅜ

hyj5419 5년 전 0

왜 시간초과가 뜨는지 모르겠습니다. ㅠㅠ

감사합니다.

#include<iostream>
#include<stdio.h>
#include<utility>
#include<vector>
#include<algorithm>
#include<stack>
#include<string.h>
using namespace std;

vector<int>adj[100];
vector<int>adj2[100];
int visit[100];
int visit2[100];
int cnt = 1;
int dfs(int v) {
	visit[v] = 1;
	cnt = 1;
	for (int i = 0; i < adj[v].size(); i++) {
		int next = adj[v][i];
		if (visit[next] != 1) {
			visit[next] = 1;
			cnt+=dfs(next);
		}
	}
	return cnt;
}
int dfs2(int v) {
	visit2[v] = 1;
	cnt = 1;
	for (int i = 0; i < adj2[v].size(); i++) {
		int next = adj2[v][i];
		if (visit2[next] != 1) {
			visit2[next] = 1;
			cnt += dfs2(next);
		}
	}
	return cnt;
}
int res[100];
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b;//a>b
		scanf("%d%d", &a, &b);
		adj[a].push_back(b);
		adj2[b].push_back(a);
	}
	int mid = (n + 1) / 2;
	for (int i = 1; i <= n; i++) {		
		int OUT = dfs(i);
		int IN = dfs2(i);
		if( OUT>mid||IN>mid)
			res[i] = 1;
		memset(visit, 0, sizeof(visit));
		memset(visit, 0, sizeof(visit2));
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (res[i] ==1) {
			ans++;
		}
	}	printf("%d\n", ans);



}

djm03178 5년 전 0

visit 배열은 구슬의 번호가 인덱스가 되어야 할 텐데, adj 배열의 인덱스에 지나지 않는 i를 가지고 20번째 줄과 32번째 줄을 검사하네요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

구슬찾기문제 시간초과 ㅜㅜ

hyj5419 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말