1 solutions
-
0
C++ :
#include<stdio.h> #include<string.h> #include<vector> using namespace std; const int MAXN = 1000010; int n, m; int c[MAXN]; int topo[MAXN], t; vector <int >G[MAXN]; bool dfs(int u){ c[u] = -1; for(int v = 0; v < n; v++) { for(vector<int>::iterator it=G[u].begin();it!=G[u].end();it++) if(*it==v) { if(c[v]<0) return false; else if(c[v]==0&&!dfs(v)) return false ; } } c[u] = 1; topo[--t]=u; return true; } bool toposort(){ t = n; memset(c, 0, sizeof(c)); for(int u = 0; u < n; u++) if(!c[u]) if(!dfs(u)) return false; return true; } int main() { while(scanf("%d%d", &n, &m)!=EOF&&!(n==0&&m==0)) { memset(G, 0, sizeof(G)); for(int i = 0; i < m; i++) { int u, v; scanf("%d%d", &u, &v); u=u-1;v=v-1; G[u].push_back(v); } if(toposort()) { for(int i = 0; i < n; i++) printf("%d\n", topo[i]+1); } else printf("IMPOSSIBLE\n"); } }
- 1
Information
- ID
- 18754
- Time
- 1000ms
- Memory
- 128MiB
- Difficulty
- (None)
- Tags
- (None)
- # Submissions
- 0
- Accepted
- 0
- Uploaded By