B - Network(tarjan求割点和桥板子)
程序员文章站
2022-06-01 11:55:52
...
https://www.luogu.com.cn/problem/UVA315
板子:
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=200;
typedef long long LL;
vector<LL>g[maxn];
LL fa[maxn],dfn[maxn],low[maxn],times=0;
bool ge[maxn];
void tarjan2(LL x)
{
dfn[x]=low[x]=++times;
LL child=0;
for(LL i=0;i<g[x].size();i++)
{
LL to=g[x][i];
if(!dfn[to])
{
child++;fa[to]=x;
tarjan2(to);
if(-1==fa[x]&&child>=2) ge[x]=true;
if(-1!=fa[x]&&low[to]>=dfn[x]) ge[x]=true;
if(low[to]>dfn[x]){
///cout<<x<<"->"<<to<<" is bridge"<<endl;
}
low[x]=min(low[x],low[to]);
}
else if(to!=fa[x]) low[x]=min(low[x],dfn[to]);
}
}
int main(void)
{
for(LL i=1;i<=n;i++) if(!dfn[i]) tarjan2(i);
}
对于算法的理解:
注意点一:第二次更新dfn不空的节点注意要min(low[x],dfn[to]);
https://blog.csdn.net/Kamisama123/article/details/75007415(这个地方的解释)
考虑这样一幅图:
假如我们用low【v】来更新low【u】,一种存在的遍历顺序会导致这样一种情况。
节点3的dfn为3,low为1,节点5的dfn为5,low为1,节点4的dfn为4,low为1。
这种情况导致3不被判定为割点。
注意点2:判断儿子和父亲的关系是在搜索树中的。所以x为root的时候且有两个儿子只有一种情况。
注意点3:x是割点.cas1:非root点&&有儿子&&low[x的儿子]>=dfn[x];
case2:root点&&有>=2个儿子
x-y是桥:low[y]>dfn[x];
复习参考视频:https://www.bilibili.com/video/BV1GE411G7Kq
关于本题:是割点的板子题。输入比较毒瘤。
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=200;
typedef long long LL;
vector<LL>g[maxn];
LL fa[maxn],dfn[maxn],low[maxn],times=0;
bool ge[maxn];
void tarjan2(LL x)
{
dfn[x]=low[x]=++times;
LL child=0;
for(LL i=0;i<g[x].size();i++)
{
LL to=g[x][i];
if(!dfn[to])
{
child++;fa[to]=x;
tarjan2(to);
if(-1==fa[x]&&child>=2) ge[x]=true;
if(-1!=fa[x]&&low[to]>=dfn[x]) ge[x]=true;
if(low[to]>dfn[x]){
///cout<<x<<"->"<<to<<" is bridge"<<endl;
}
low[x]=min(low[x],low[to]);
}
else if(to!=fa[x]) low[x]=min(low[x],dfn[to]);
}
}
int main(void)
{
///cin.tie(0);std::ios::sync_with_stdio(false);
LL n;
while(cin>>n&&n)
{
memset(fa,-1,sizeof(fa));memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));memset(ge,0,sizeof(ge));
times=0;
for(LL i=0;i<=n+10;i++) g[i].clear();
LL sz;
while(cin>>sz&&sz)
{
while(1)
{
char ch=getchar();if(ch=='\n') break;
LL v;cin>>v;
g[sz].push_back(v);g[v].push_back(sz);
}
}
LL sum=0;
for(LL i=1;i<=n;i++) if(!dfn[i]) tarjan2(i);
for(LL i=1;i<=n;i++) if(ge[i]) sum++;
cout<<sum<<endl;
}
return 0;
}
上一篇: 对Java内存模型的理解
下一篇: linux查找php.ini方法