POJ2553

SP1799

我们知道单独一个强连通分量中的所有点是满足题目要求的

但如果它连出去到了其他点那里，要么成为新的强连通分量，要么失去原有的符合题目要求的性质

所以只需tarjan缩点求出所有强连通分量，再O(E)枚举所有边，是否会成为连接一个分量与另一个分量的边——即一条出度——即可

如果一个分量没有出度，那么他中间的所有点都是符合题目要求的点

（因为快读快输加了太长所以就不贴了）

const int N=5005,M=N*N>>1;

int h[N],en,n,m,dfn[N],out[N],bel[N],low[N],num,cnt;

stack<int> st;

struct edge{int n,u,v;}e[M]; //前向星存边

inline void add(const int &x,const int &y){e[++en]=(edge){h[x],x,y},h[x]=en;}

inline void tarjan(int x){ //一个tarjan缩点STL栈模板

    st.push(x);

    dfn[x]=low[x]=++num;

    for(int i=h[x];i;i=e[i].n){

        int y=e[i].v;

        if(!dfn[y]){

            tarjan(y);

            low[x]=min(low[x],low[y]);

        }

        else if(!bel[y])

            low[x]=min(low[x],dfn[y]);

    }

    if(low[x]==dfn[x]){

        cnt++;

        int TOP;

        do{

            TOP=st.top();

            st.pop();

            bel[TOP]=cnt;

        }while(TOP!=x);

    }

}

signed main(){

    read(n);

    while(n){

        en=num=cnt=0;

        memset(h,0,sizeof h);

        memset(dfn,0,sizeof dfn);

        memset(out,0,sizeof out);

        memset(bel,0,sizeof bel);

        memset(low,0,sizeof low);

        read(m);

        while(m--){

            int x,y;

            read(x),read(y);

            add(x,y);

        }

        for(int i=1;i<=n;i++) if(!dfn[i]) //跑缩点

            tarjan(i);

        for(int i=1,u,v;i<=en;i++){

            u=e[i].u,v=e[i].v;

            if(bel[u]!=bel[v]) out[bel[u]]++; //判断每条边的起点终点是否在同一强连通分量中，如果不是，则起点所在强连通分量出度加1

        }

        for(int i=1;i<=n;i++) if(!out[bel[i]]) //如果点i所在强连通分量没有出度则满足要求，输出

            Write(i,' ');

        printf("\n"); //统一换行

        read(n);

    }

}

巴特西

POJ2533&&SP1799 The Bottom of a Graph(tarjan+缩点)

POJ2553

SP1799

最新文章

热门文章