首页 > 代码库 > 炸铁路

炸铁路

https://www.luogu.org/problem/show?pid=1656

#include <algorithm>#include <iostream>using namespace std;int n,m,x,y,tot,tott;int fa[100015];struct node{    int a,b;}w[100015];struct nodee {    int u,v,l;}e[100015];void add_in(int x,int y,int z){    fa[x]=y;    tot++;    e[tot].u=x;    e[tot].v=y;    e[tot].l=z;}void add_out(int x,int y){    tott++;    w[tott].a=x;    w[tott].b=y;}int find(int x){    if(x!=fa[x])        return fa[x]=find(fa[x]);    return x;}bool cmp(node x,node y){    if(x.a==y.a)        return x.b<y.b;    else    return x.a<y.a;}int main(){    cin>>n>>m;    for(int i=1;i<=n;i++)    fa[i]=i;    for(int i=1;i<=m;i++)    {        cin>>x>>y;        add_in(x,y,1);    }    for(int i=1;i<=tot;i++)    {        for(int j=1;j<=tot;j++)                e[i].l=1;        if(e[i].l==1)        {            fa[e[i].u]=e[i].u;            e[i].l==0;            if(find(e[i].u)==e[i].u)                add_out(e[i].u,e[i].v);        }            }    sort(w+1,w+tott+1,cmp);    for(int i=1;i<=tott;i++)        cout<<w[i].a<<" "<<w[i].b<<endl;    return 0;}

 

炸铁路