1 solutions

  • 0
    @ 2025-11-5 18:04:14

    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