v 0. Pasted by slipstak2 as cpp at 2011-01-11 20:18:28 MSK and set expiration to never.

Paste will expire never.

  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. enum VERTEX_TYPE{WHITE,GRAY,BLACK};
  6. int n;
  7. vector<vector<int> > adj;
  8. vector<VERTEX_TYPE> used;
  9. void input() {
  10.     cin>>n;
  11.     adj.resize(n*n);
  12.     used.resize(n*n,WHITE);
  13.     char c;
  14.     int row,col,f,s;
  15.     int len = 2*(n*n-n);
  16.     for (int i=0;i<len;i++) {
  17.         cin>>c;
  18.         row = i / (2*n - 1);
  19.         col = i % (2*n - 1);
  20.         f = row*n + col;
  21.         if (c == '>' || c == '<') {
  22.             s = f + 1;
  23.             if (c == '>')
  24.                 adj[f].push_back(s);
  25.             else
  26.                 adj[s].push_back(f);
  27.         }
  28.         else {
  29.             f-= n - 1;
  30.             s = f + n;
  31.             if (c == 'v')
  32.                 adj[f].push_back(s);
  33.             else
  34.                 adj[s].push_back(f);
  35.         }
  36.     }
  37. }
  38. bool dfs(int cur, vector<int> &ans) {
  39.     used[cur] = GRAY;
  40.     for (int i=0;i<adj[cur].size();i++) {
  41.         int next = adj[cur][i];
  42.         if (used[next] == GRAY)
  43.             return false;
  44.         if (used[next] == WHITE) {
  45.             if (!dfs(next,ans))
  46.                 return false;
  47.         }
  48.     }
  49.     used[cur] = BLACK;
  50.     ans.push_back(cur);
  51.     return true;
  52. }
  53. bool topological_sort(vector<int> &ans) {
  54.     for (int i=0; i<n*n; i++) {
  55.         if (used[i] == WHITE) {
  56.             if (!dfs(i,ans))
  57.                 return false;
  58.         }
  59.     }
  60.     return true;
  61. }
  62. void solve()
  63. {
  64.     vector<int> ans;
  65.     vector<int> out;
  66.     if (!topological_sort(ans)) {
  67.         cout<<-1;
  68.         return;
  69.     } else {
  70.  
  71.         out.resize(ans.size());
  72.         for (int i=0;i<ans.size();i++)
  73.             out[ans[i]] = i+1;
  74.     }
  75.     int pos = 0;
  76.     for (int i=0;i<n;i++){
  77.         for (int j=0;j<n;j++)
  78.             cout<<out[pos++]<<' ';
  79.         cout<<endl;
  80.     }
  81. }
  82. int main() {
  83.     /*freopen("input.txt","r",stdin);
  84.     freopen("output.txt","w",stdout);*/
  85.  
  86.     input();
  87.     solve();
  88.     return 0;
  89. }


Editing is locked.