题解 P1656 【炸铁路】

刚看这题时，只觉得这题怎么这么简单，记一下入度为0的点不就ok了？然后就火急的跑去敲代码，一交，怎么才拿了一个点？？回去好好看题目又结合题解，我才知道这是找割线(佩服自己的读题能力……)。不过这题其实不用什么并查集压缩或是什么Tu啥的算法，因为数据比较小，我们可以直接枚举每一条边，并割掉它，然后就遍历一遍图，看能否连通，不行就加到keyroad里面，具体还是看代码吧 ```cpp #include<cstdio> #include<algorithm> using namespace std; struct bi{//用来记录keyroad的结构体，定结构体主要是为了排序方便 int x,y; }; bi b[5010]; int a[200][5010],c[200][200],v[200];//这里我用的是邻接矩阵存储，主要是因为我邻接表打的不多，怕一不小心就搞错，就用了矩阵 int comp(bi c,bi d)//sort的comp函数，定义如何排序结构体，其实也可以在结构体里重载<来实现，不过一般我习惯用comp { if(c.x==d.x) return c.y<d.y; return c.x<d.x; } void dfs(int x)//用深搜遍历整个图 { int i; v[x]=1;//记录这个点已经走过 for(i=1;i<=a[x][0];i++)//把能走的点全部走一边 if(!v[a[x][i]]) dfs(a[x][i]); return; } int main() { int i,j,n,m,x,y,k,l=0,p; scanf("%d%d",&n,&m); for(i=1;i<=m;i++) { scanf("%d%d",&x,&y); a[x][++a[x][0]]=y;//为了节约空间就用无用的0下标来储存度 a[y][++a[y][0]]=x; } for(i=1;i<=n;i++)//开始枚举每条边 for(j=1;j<=a[i][0];j++) if(a[i][j]&&!c[i][a[i][j]]&&!c[a[i][j]][i])//如果有路且没有删过 { c[i][a[i][j]]=c[a[i][j]][i]=1;//c数组是用来记录这条边有没有被删过，因为图是无向图，以减少枚举数量 for(k=1;k<=a[a[i][j]][0];k++)//找到对应的点所指向这个点的下标 if(a[a[i][j]][k]==i) break; p=a[i][j];//记录原来对应点 a[i][j]=a[p][k]=0;//删去这条边，因为没有0这个点，所以定为0 dfs(1);//深搜遍历 a[i][j]=p;//回溯，把边连回上去 a[p][k]=i; p=0; for(k=1;k<=n;k++)//搜每个点，看有没有经过，没有就说明这条边是keyroad，将其加入答案，同时进行v数组清零 { if(!v[k]&&!p) { b[++l].x=min(i,a[i][j]); b[l].y=max(a[i][j],i); p=1; } v[k]=0; } } sort(b+1,b+l+1,comp);//排序答案 for(i=1;i<=l;i++) printf("%d %d\n",b[i].x,b[i].y);//最后输出，end return 0; } ```