首页 > 代码库 > 图的割点 | | jzoj【P1230】 | | gdoi | |备用交换机
图的割点 | | jzoj【P1230】 | | gdoi | |备用交换机
写在前面：我真的不知道图的割点是什么。。。。
看见ftp图论专题里面有个dfnlow的一个文档，于是怀着好奇的心情打开了这个罪恶的word文档，，然后就开始漫长的P1230的征讨战。。。。
图的割点是这样的：
path1=暴力
枚举每一个点，如果去掉这个点就可以使图断开，那么这个点就是割点（时间复杂度O(N(N+M))）
path2=tarjan
从任意一个点开始遍历，记录遍历的顺序，然后对正在遍历的点进行一次深度优先遍历，但是此次遍历不允许经过这个点，看看还能不能回到前一个点
这时候我们就可以再定义一个数组low，这个数组用来记录每个顶点在不经过前一个遍历的顶点时，能够回到的最近（就是截止到此顶点最后被遍历）的结点
如果存在一个顶点u，图中一个顶点v满足low[v]>=num[u]（num是遍历的顺序），那么u就是割点
problem set：
n个城市之间有通讯网络，每个城市都有通讯交换机，直接或间接与其它城市连接。因电子设备容易损坏，需给通讯点配备备用交换机。但备用 交换机数量有限，不能全部配备，只能给部分重要城市配置。于是规定：如果某个城市由于交换机损坏，不仅本城市通讯中断，还造成其它城市通讯中断，则配备备 用交换机。请你根据城市线路情况，计算需配备备用交换机的城市个数，及需配备备用交换机城市的编号。
很明显这个题是割点：
但是有一个坑~~
最开始写的是邻接矩阵，，看看能不能过，想着邻接矩阵能过小数据以后改成邻接表就能过大数据了
然而最开始还是too young
别忘了题目描述里并没有说图一定联通；
也就是说我们必须对每一个点都进行遍历，而且不要忘了对根节点的判断。。。
代码实现如下
#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>using namespace std;int n,m,root;int num[500000],low[500000],flag[500000],index;//index==++int in[500000],stack[500000];int sum=0;struct edge{ int y,next;}e[500000];int len=0;int link[500000];void insert(int xx,int yy){ e[++len].next=link[xx];link[xx]=len; e[len].y=yy; }int top;void dfs(int cur){ int v; num[cur]=low[cur]=++index; stack[++top]=cur; in[cur]=1; int temp=0; for(int i=link[cur];i;i=e[i].next) { v=e[i].y; if(!num[v]) { dfs(v); temp++; low[cur]=min(low[cur],low[v]); //if(low[v]>=num[cur]&&cur!=1) // flag[cur]++; if((cur==root && temp>1)||(cur!=root && low[v]>=num[cur])) if(!flag[cur]) flag[cur]++,sum++; } else if(in[v]) low[cur]=min(low[cur],num[v]); } if(low[cur]==num[v]) { while(cur!=v) { v=stack[top--]; in[v]=0; } }}int main(){ //freopen("a.in","r",stdin); //freopen("a.out","w",stdout); int x,y; cin>>n; while(cin>>x>>y) { insert(x,y); insert(y,x); } for(int i=1;i<=n;i++) { if(!num[i]) { root=i; dfs(i); } } cout<<sum<<endl; for(int i=1;i<=n;i++) { if(flag[i]) cout<<i<<endl; } return 0;}
图的割点 | | jzoj【P1230】 | | gdoi | |备用交换机