2개의 댓글이 있습니다.

• 
  Signin

  • 알고스팟에서 다른 사람의 소스 코드는 풀기 전까지 원칙적으로 비공개인 것으로 알고 있습니다.
  • 이런 경우 소스코드를 함께 올려주시면 다른 분들이 알기 쉽습니다.

  
  10년 전 link

• 
  best88

  제출했던 소스입니다ㅠㅠ
  도움 주시면 감사하겠습니다 ㅠㅠ

  vector words;
  vector> adj;
  vector order, rev_order, seen;

  void makegraph()
  {
  adj = vector>(26, vector(26,0));

  for(int j = 1; j < words.size() ; ++j)
  {
      int i = j - 1; int len = min(words[i].size(), words[j].size());
  
      for(int x = 0 ; x < len ; ++x)
      {
          if(words[i][x] != words[j][x])
          {
              int a = words[i][x] - 'a';
              int b = words[j][x] - 'a';
              adj[a][b] = 1; 
              break;
          }
      }
  }
  

  }
  void dfs(int here)
  {
  seen[here] = 1;

  for(int there = 0 ; there < adj.size() ; there++)
      if(adj[here][there] && !seen[there])
          dfs(there);     
  order.push_back(here);
  

  }

  vector topologicakSort()
  {
  int n = adj.size();
  seen = vector(n, 0);
  order.clear();

  for(int i = 0 ; i < n ; ++i)
  {
      if(!seen[i])
          dfs(i);
  }
  reverse(order.begin(), order.end());
  
  for(int i = 0 ; i < n ; ++i)
      for(int j = i + 1 ; j < n ; ++j)
          if(adj[order[j]][order[i]])
              return vector<int>();
  
  return order;
  

  }

  int main()
  {
  int _case, _word;
  string word;

  cin>>_case;
  for(int i = 0 ; i < _case ; i++)
  {
      cin>>_word; 
      for(int j  = 0 ; j < _word ; j++)
      {
          cin>>word;
          words.push_back(word);
      }
      makegraph();
      vector<int> ref = topologicakSort();
      if(ref.size() == 0)
      {
          cout<<"INVALID HYPOTHESIS"<<endl;           
      }
      else
      {
          for(int x = 0 ; x < ref.size() ; x++)
          {           
              char temp = 'a' + ref[x];
              cout<<temp;
          }
      }
  }   
  return 0;
  

  }

  
  10년 전 link

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