15개의 댓글이 있습니다.

• 
  도토리

  처음에 들어가는 값이 학생의 수 인것은 알겠는데 그 다음 친구 쌍의 수와 서로 친구인 두 학생의 번호가 무슨 의미인지 이해가 가지 않습니다. 저의 부족한 이해력에 도움 주시면 감사하겠습니다

  
  9년 전 link

• 
  chaos.kite

  두번째 case 4,6인 경우
  학생수는 4명, 6쌍의 친구가 있습니다.
  6쌍의 친구는 그아래 line에 적혀 있네요.
  괄호안에 학생들은 친구 입니다.
  (0, 1) (1, 2) (2, 3) (3, 0) (0, 2) (1, 3)

  
  9년 전 link

• 
  hn.kim

  0 이라는 번호를 가진 사람과 1 이라는 번호를 가진 사람이 친구라는 쌍을 이루었다라는 뜻으로 이런 쌍이 6쌍 있다라는 뜻입니다.

  
  8년 전 link

• 
  sksmsvlxk

  예제 입력 이해하는데 한참 걸렸네요..
  예제 입력에서 테스트 케이스와 서로 친구인 두 학생의 번호가 이렇게 구성되어있는거네요.

  3 테스트케이스 개수
  2 1 학생 수와 짝 수( 학생 둘, 친구 한쌍 )
  0 1 0번학생과 1번학생( 학생이 둘이고 이 둘이 친구 )
  ------------------------ 여기까지 해서 테스트 케이스 1
  4 6 학생 넷, 친구 여섯 쌍.
  0 1 1 2 2 3 3 0 0 2 1 3 0과 1이 친구, 1과 2가 친구, 2와 3이 친구 등등등
  ------------------------ 여기까지 해서 테스트 케이스 2

  이런 식이네요.

  처음에 테스트 케이스가 3개 라고 해서
  2 1
  0 1
  4 6
  이렇게 케이스가 3개인 걸로 생각해서 한참 생각했네요.

  
  8년 전 link

• 
  jy.hwang

  예제 출력이 1 2 4 네요 ㅠ

  
  8년 전 link

• 
  kevin13

  @jy.hwang님, 예제 2번째의 출력이 3이 맞습니다. 다음의 쌍으로 구성됩니다.

  (0, 1), (2, 3),
  (1, 2), (3, 0),
  (0, 2), (1, 3)

  jy.hwnag님 프로필을 보니 PICNIC 문제를 푸신 걸로 나오는데... 아마도 테스트 상의 운이 좋으셨던 것이 아닌가 생각됩니다.

  
  8년 전 link

• 
  fkdlslss

  이거 재귀로 하려고 배열안에 학생들을 줄세워놓고 next_permutation을 사용하려고 하니까 제출할때 안되네여 ;; 여기서 백터나 perutation 사용하면 안돠ㅣ나여??;;

  
  8년 전 link

• 
  astein

  next_permutation은 algorithm 헤더를 include 해야 사용할 수 있습니다.

  
  8년 전 link

• 
  astein

  직접 코드를 찾아서 디버깅을 해 드리기는 곤란해서.... ㅠ;;;

  
  8년 전 link

• 
  SeungYoun

  #include

  int ret[50]={0,};
  bool are_friends[10][10];
  bool is_selected[10]={false,};

  int solve(bool is_selected[10], int n){
  int i,a;
  for(i=0;i<n;i++){
  if(!is_selected[i]){
  a = i;
  is_selected[i] = true;
  break;
  }
  return 1;
  }
  int ret =0;
  for(i=a+1;i<n;i++){
  if(!is_selected[i] && are_friends[a][i]){
  is_selected[i] = true;
  
  ret += solve(is_selected,n);
  is_selected[i]=is_selected[a]=false;
  }
  }
  return ret;
  }

  int main(){
  int i,j,C,tmp1,tmp2,m,n;
  scanf("%d",&C);
  for(i=0;i<C;i++){
  scanf("%d %d",&n,&m);
  for(j=0;j<m;j++){
  scanf("%d %d",&tmp1,&tmp2);
  are_friends[tmp1][tmp2] = are_friends[tmp2][tmp1] = true;
  }
  ret[i] = solve(is_selected,n);
  }
  for(i=0;i<C;i++){
  printf("%d\n",ret+i);
  }
  return 0;
  }

  제 코드인데 main함수 부분에서 input데이터를 받는 부분이 잘 처리가
  되질 않는것 같은데 이유를 모르겠습니다. input데이터를 프린트를 해보면

  for(j=0;j<m;j++){
  scanf("%d %d",&tmp1,&tmp2);

  이 부분에서 tmp1은 잘 저장이 되는데 tmp2는 저장이 되질 않습니다 ㅠㅠ

  
  8년 전 link

• 
  cosics

  너무 어렵게 풀이를 시도했네요.. 간단한 플랙을 사용하는게 더 간단하고 빠른 방법이네요.. 시간초과로 몇 번을 실패했고 지금도 시간초과가 나는데.. 정답은 이렇게 간단하고 쉽네요^^ 좀 고정관념.. 문제를 너무 어렵게 생각하는 그런 고정관념을 버려야 할 것 같습니다.

  
  7년 전 link

• 
  polaris6921

  ubuntu 14.04에서는 무사히 컴파일이 되고 실행이 되는데,

  채점을 하려고 하면 RTE에러가 발생해서 런타임에 죽네요. 혹시나해서 array를 넘길 때 그 사이즈도 같이 넘겨주는데, 이렇게 해도 문제가 계속 발생해서 풀 수가 없습니다.

  
  6년 전 link

• 
  dbfldkfdbgml

  혹시 union find로 비슷하게 풀리면 틀리는데요. 왜 틀리는지 알 수 있을까요?

  
  4년 전 link

• 
  dbfldkfdbgml

  #include
  #include
  #include
  #include
  #include
  #include
  #include
  #include
  #include
  #include

  //namespaces
  using namespace std;

  //variables
  int C, N, M;
  int answer;

  //pointer variables
  int * parents;
  bool * visited;

  //comparator

  //method
  void merge(int a, int b);
  int find(int a);

  int find(int a) {
  if (parents[a] == a) {
  return a;
  }
  return parents[a] = find(parents[a]);
  }

  void merge(int a, int b) {
  int root_a = find(a);
  int root_b = find(b);
  if (root_a < root_b) {
  parents[root_b] = root_a;
  } else {
  parents[root_a] = root_b;
  }
  }

  void dfs(int a, int b, int number) {
  if (number == N) {
  for (int i = 1; i <= N; i++) {
  if (visited[i] == false) {
  return;
  }
  }
  answer++;
  return;
  }

  int idx = -1;
  for (int i = 1; i <= N; i++) {
      if (visited[i] == false) {
          idx = i;
          break;
      }
  }
  
  for (int i = idx + 1; i <= N; i++) {
      if (parents[idx] == parents[i] && visited[i] == false) {
          visited[idx] = true;
          visited[i] = true;
          dfs(idx, i, number + 2);// 1 and i are friends, and the number of the friends is 2
          visited[idx] = false;
          visited[i] = false;
      }
  
  }

  }

  //main method
  int main() {

  //speedy reading option
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);
  
  //new part
  cin >> C;
  int a, b;
  for (int test_case = 0; test_case < C; test_case++) {
      cin >> N >> M;
      parents = new int[N + 1];
      visited = new bool[N + 1];
  
      answer = 0;
      for (int i = 0; i <= N; i++) {
          parents[i] = i;
          visited[i] = false;
      }
      for (int i = 0; i < M; i++) {
          cin >> a >> b;
          merge(a + 1, b + 1);
      }
      for (int i = 1; i <= N; i++) {
          cout << parents[i] << " ";
      }
      cout << "\n";
  
      for (int j = 1; j <= 1; j++) {
          for (int i = j + 1; i <= N; i++) {
              if (parents[j] == parents[i] && visited[i] == false) {
                  visited[j] = true;
                  visited[i] = true;
                  dfs(j, i, 2);// 1 and i are friends, and the number of the friends is 2
                  visited[j] = false;
                  visited[i] = false;
                  break;
              }
          }
      }
      cout << answer << "\n";
  }
  return 0;

  }

  
  4년 전 link

• 
  asd930817

  예전에 풀어봤던 문제인데 계속 오답이네요... 혹시 제 코드에서 코너케이스 알수있을까요? 어떤 예제를 넣어도 문제가없는데 이상하네요

  
  11달 전 link

• 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.