글 읽기 - 접근방법좀가르주세요 ㅠ

kdhsong 8년 전 0

시간초과뜨는 방법밖에생각이안나네여 ...

ㅠ

iriszero 8년 전 0

완전 탐색으로 하셔도 잘만 짜면 2700ms 정도에 accepted 받으실 수 있고,

더 빠른 방법 원하시면 SCC (strongly connected component) 검색해보세요.

kdhsong 8년 전 0

DFS로 짯는데 시간초과가 떳는데

좀봐주실수있나요 ?..

#include <stdio.h>
#include <vector>
#define MAX(a,b)	a>b?a:b

using namespace std;
vector<int> v[10001];
int ret = 0;
int save[10001];
bool check[10001];
int dfs(int start){
	
	int size = v[start].size();
	if(size == 0)	return 1;
	
	int sum = 1;
	for(int i = 0; i < size; i++){
		if(check[v[start].at(i)])	continue;
		check[start]=true;

		int d = dfs(v[start].at(i));
		sum+=d;

		check[start]=false;
	}

	return sum;
}

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

	for(int i = 0; i < m; i++){
		int a,b;
		scanf("%d %d",&a,&b);
		v[b].push_back(a);
	}
	
	for(int i = 1; i <= n; i++){
		save[i] = dfs(i);
		ret = MAX(ret,save[i]);
	}

	for(int i = 1; i <= n; i++)
		if(ret == save[i])	printf("%d ",i);
}

kdhsong 8년 전 0

완전탐색으로 어떻게한다는건가염?

chatterboy 8년 전 0

위처럼 dfs를 하면 AC를 받을 수 있어요. 그리고 저도 이유는 모르겠지만 전역 배열들을 사용하지 않고 STL vector를 사용한 경우 AC를 받았습니다.

kdhsong 8년 전 0

안되네요 잘 흑흐규ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

전 이상하게돌린건가..

#include <stdio.h>
#include <vector>
#define MAX(a,b)	a>b?a:b

using namespace std;
vector<int> v[10001];
int ret = 0;
bool check[10001];
int dfs(int start){
	
	int size = v[start].size();
	if(size == 0)	return 1;
	
	int sum = 1;
	for(int i = 0; i < size; i++){
		if(check[v[start].at(i)])	continue;
		check[start]=true;

		int d = dfs(v[start].at(i));
		sum+=d;

		check[start]=false;
	}

	return sum;
}

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

	for(int i = 0; i < m; i++){
		int a,b;
		scanf("%d %d",&a,&b);
		v[b].push_back(a);
	}
	
	vector<int> save;
	for(int i = 1; i <= n; i++){
		int t = dfs(i);
		save.push_back(t);
		ret = MAX(ret,t);
	}

	for(int i = 0; i < save.size(); i++)
		if(ret == save.at(i))	printf("%d ",i+1);
}

chatterboy 8년 전 0

무슨 차이가 크게 나길래 그런지는 모르겠어요. 한번 확인해보시길...

#include <stdio.h>
#include <cstring>
#include <vector>
#define MAX(a,b)    a>b?a:b
 
using namespace std;
// vector<int> v[10001];
vector<vector<int>> v;
int ret = 0;
int save[10001];
// bool check[10001];
vector<bool> check;
int dfs(int start){
/*     
    int size = v[start].size();
    if(size == 0)   return 1;
  */
    check[start] = true;
    int sum = 1;
//	for (int i = 0; i < size; i++) {
    for(int i = 0; i < v[start].size(); i++){
//        if(check[v[start].at(i)])   continue;
 		int there = v[start][i];
 		if (!check[there]) sum += dfs(there);
 //       int d = dfs(v[start].at(i));
//        sum+=d;
 
    }
    return sum;
}
 
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
 	v.resize(n + 1);
    for(int i = 0; i < m; i++){
        int a,b;
        scanf("%d %d",&a,&b);
        v[b].push_back(a);
    }
/*
    for(int i = 1; i <= n; i++){
        save[i] = dfs(i);
        ret = MAX(ret,save[i]);
    }
 
    for(int i = 1; i <= n; i++)
        if(ret == save[i])  printf("%d ",i);
  */ 

    vector<int> ans;
    int mx = 0;
    for (int i = 1; i <= n; i++) {
    	check = vector<bool>(n + 1, false);
    	int res = dfs(i);
    	if (ans.empty() || mx == res) {
    		ans.push_back(i);
    		mx = res;
    	} else if (mx < res) {
    		ans.clear();
    		ans.push_back(i);
    		mx = res;
    	}
    }

    for (auto b : ans) printf("%d ", b);

}

kdhsong 8년 전 0

chatterboy님 도움주셔서 너무감사드립니다..! 감사합니다!

kdhsong 8년 전 0

chatterboy님 근데 다돌리면 시간복잡도 O(nm)인데 돌려도되나요 ?ㅠ아직 감이잘안잡혀서 ㅠㅠㅠ

chatterboy 8년 전 0

문제를 풀었을 당시에는 몰랐었는데 생각해보니 TLE가 안 나는게 신기하네요.. ㅋㅋ

저도 감이 안 잡혀요 ㅜㅜ

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

문제

문제

출처

ICPC

접근방법좀가르주세요 ㅠ

kdhsong 8년 전 0

iriszero 8년 전 0

kdhsong 8년 전 0

kdhsong 8년 전 0

chatterboy 8년 전 0

kdhsong 8년 전 0

chatterboy 8년 전 0

kdhsong 8년 전 0

kdhsong 8년 전 0

chatterboy 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말