#include #include #include #include #define INPROCESS 1 #define FINISHED 2 #define NOTFINISHED 0 #define ON 1 #define OFF 0 using namespace std; typedef vector ADJLIST; struct vert{ int vnum,val,time; char color; }; struct vert* ans; int n,t; ADJLIST* vmat; void print_exit() { cout << "0"; exit(1); } void DFS(int x) { ADJLIST::iterator itr; if(ans[x].color == FINISHED) return; ans[x].color = INPROCESS; for(itr=vmat[x].begin();itr != vmat[x].end();itr++){ if(ans[*itr].color == INPROCESS)//its a cycle-->no topological ordering exists print_exit(); if(ans[*itr].color == NOTFINISHED) DFS(*itr); } ans[x].color = FINISHED; ans[x].vnum = x; ans[x].time = t++; } int compare(const void* a,const void* b) { return(((struct vert*)a) ->time - ((struct vert*)b) ->time); } int compare2(const void* a,const void* b) { return(((struct vert*)a) ->vnum - ((struct vert*)b) ->vnum); } void findans() { int i = 0; for(i = 1;i <= n;i++) if(ans[i].color == NOTFINISHED) DFS(i); qsort(ans,n+1,sizeof(vert),compare);//sort based on finish time for(i = 1;i <= n;i++) ans[i].val = i; qsort(ans,n+1,sizeof(vert),compare2);//sort based on the vertex number cout << "1\n"; int count = 1,x,xlim=1; for(;;){ for(x = 0;x < xlim;x++,count++){ cout << ans[count].val; if(x != xlim-1) cout << " "; } if(count > n) break; cout << "\n"; xlim += 2; } } int main() { int i = 0,lim = 0,j = 0,diff = 2,count = 1; cin >> n; char adjstr[200],verstr[200]; lim = (2*n) - 2; int temp,len,flag = ON; n *= n;//nsquare triangles-->each triangle represents a vertex vmat = new ADJLIST[n+1]; ans = new vert[n+1]; ans[0].time=-2; ans[1].color = NOTFINISHED; //first row cin >> verstr; if(count+diff <= n) verstr[0] == '>' ? vmat[count].push_back(count+diff) : vmat[count+diff].push_back(count); //other rows for(i = 1,count = 2,diff+=2;i < lim-1;i+=2,diff+=2){ cin >> adjstr >> verstr; temp = count; len = strlen(adjstr); for(j = 0;j < len;j++,count++) adjstr[j] == '>' ? vmat[count].push_back(count+1) : vmat[count+1].push_back(count); count = temp; len = strlen(verstr); flag = ON; for(j = 0;j < len;j++,count++){ ans[count].color = NOTFINISHED; if(count+diff > n ) continue; if(flag == OFF){ flag = ON; j--; continue; } verstr[j] == '>' ? vmat[count].push_back(count+diff) : vmat[count+diff].push_back(count); flag = OFF; } } //last row cin >> adjstr; len = strlen(adjstr); for(i = 0;i < len;i++,count++){ ans[count].color = NOTFINISHED; adjstr[i] == '>' ? vmat[count].push_back(count+1) : vmat[count+1].push_back(count); } t = 1; findans(); return 0; }