#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<cmath> #include<queue> using namespace std; queue<int> q; int tot,to[200001],fi[200001],ne[200001],n,m,n1,n2; int ans[100001]; int add(int x,int y)//建立一条由x指向y的边 { to[++tot]=y; ne[tot]=fi[x]; fi[x]=tot; return 0; } int main() { scanf("%d%d",&n,&m); for(int i=0;i<m;i++) { scanf("%d%d",&n1,&n2); add(n2,n1);//反向加边 } for(int i=n;i>0;i--) { if(!ans[i])//对于每一个终点i，看有多少点的终点是他 { ans[i]=i; q.push(i);//i入队 while(!q.empty())//只要队列中还有元素 { int x=q.front();//取对首元素，将所有到这个点的点入队 q.pop(); for(int j=fi[x];j;j=ne[j]) if(!ans[to[j]]) { q.push(to[j]); ans[to[j]]=i; } } } } for(int i=1;i<=n;i++) printf("%d ",ans[i]); return 0; }不用queue的STL实现这个代码

以下是不用queue的STL实现此代码的方式：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>

using namespace std;

int tot,to[200001],fi[200001],ne[200001],n,m,n1,n2;
int ans[100001],vis[100001];

int dfs(int x) {
    vis[x] = 1;
    for(int j=fi[x];j;j=ne[j]) {
        int y = to[j];
        if(!vis[y]) {
            ans[y] = ans[x];
            dfs(y);
        }
    }
    return 0;
}

int main() {
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++) {
        scanf("%d%d",&n1,&n2);
        to[++tot]=n1;
        ne[tot]=fi[n2];
        fi[n2]=tot;
    }
    for(int i=n;i>0;i--) {
        if(!ans[i]) {
            ans[i]=i;
            dfs(i);
        }
    }
    for(int i=1;i<=n;i++)
        printf("%d ",ans[i]);
    return 0;
}

注意：这里使用了深度优先搜索（DFS）代替广度优先搜索（BFS），因此需要在dfs函数中设置vis数组来记录每个点是否访问过，防止死循环。