题解 P1656 【炸铁路】
Iowa_BattleShip
2017-10-28 09:37:01
刚看这题时,只觉得这题怎么这么简单,记一下入度为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;
}
```