1234567891011121314151617181920212223 |
- //
- struct edge { int v, next; };
- bool TopSortDFS(int v, edge e[], int g[], int u[], int &m) {
- u[v] = -2;
- for(int i = g[v]; i != -1; i=e[i].next)
- if(u[e[i].v]==-2)
- return false;
- else if(u[e[i].v]==-1 && !TopSortDFS(e[i].v, e, g, u, m))
- return false;
- u[v] = --m;
- return true;
- }
- bool TopSort(edge e[], int g[], int n, int list[]) {
- static int u[maxn];
- int m = n;
- memset(u, 255, sizeof(u));
- for(int i = 0; i < n; i++)
- if(u[i] == -1 && !TopSortDFS(i,e,g,u,m))
- return false;
- for(int i = 0; i < n; i++)
- list[u[i]] = i;
- return true;
- }
|