(连通图 模板题 无向图求割点)Network --UVA--315(POJ--1144)

链接:

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=251

http://poj.org/problem?id=1144

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=82833#problem/B

首先输入一个N(多实例,0结束),下面有不超过N行的数,每行的第一个数字代表后面的都和它存在边,0表示行输入的结束

代码:

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define maxn 10005 int dfn[maxn];///代表最先遍历到这个点的时间
int low[maxn];///这个点所能到达之前最早的时间点
int Father[maxn];///保存这个节点的父亲节点
int n, m, Time, top;///Time 时间点, top用于栈操作
vector<vector<int> > G; void Init()
{
G.clear();
G.resize(n+);
memset(low, , sizeof(low));
memset(dfn, , sizeof(dfn));
memset(Father, , sizeof(Father));
Time = ;
} void Tarjan(int u,int fa)
{
low[u] = dfn[u] = ++Time;
Father[u] = fa;
int len = G[u].size(), v; for(int i=; i<len; i++)
{
v = G[u][i]; if(!dfn[v])
{
Tarjan(v, u);
low[u] = min(low[u], low[v]);
}
else if(fa != v)///假如我们在这里写上了 low[u] = min(low[v], low[u]),那么就相当于我们由v回到了v之前的节点
low[u] = min(dfn[v], low[u]);
}
}
void solve()
{/**
求割点
一个顶点u是割点,当且仅当满足(1)或(2)
(1) u为树根,且u有多于一个子树。
(2) u不为树根,且满足存在(u,v)为树枝边(或称 父子边,即u为v在搜索树中的父亲),使得 dfn(u)<=low(v)。
(也就是说 V 没办法绕过 u 点到达比 u dfn要小的点)
注:这里所说的树是指,DFS下的搜索树*/
int RootSon = , ans = ;///根节点儿子的数量
bool Cut[maxn] = {false};///标记数组,判断这个点是否是割点 Tarjan(,); for(int i=; i<=n; i++)
{
int v = Father[i];
if(v == )///也是就说 i的父亲是根节点
RootSon ++;
else if(dfn[v] <= low[i])
Cut[v] = true;
} for(int i=; i<=n; i++)
{
if(Cut[i])
ans ++;
}
if(RootSon > )
ans++; printf("%d\n", ans);
}
int main()
{
while(scanf("%d", &n), n)
{
int a, b;
char ch;
Init();
while(scanf("%d", &a), a)
{
while(scanf("%d%c",&b,&ch))
{
G[a].push_back(b);
G[b].push_back(a);
if(ch == '\n')
break;
}
}
solve();
}
return ;
}
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std; #define N 105 struct Edage
{
int v, next;
} e[N*N]; int n, m, Index, ans;
int low[N], dfn[N], father[N], Head[N]; void Init()
{
ans = Index = ;
memset(low, , sizeof(low));
memset(dfn, , sizeof(dfn));
memset(father, , sizeof(father));
memset(Head, -, sizeof(Head));
}
void Add(int u, int v)
{
e[ans].v = v;
e[ans].next = Head[u];
Head[u] = ans++;
}
void Tarjan(int u, int fa)
{
int v;
low[u] = dfn[u] = ++Index;
father[u] = fa; for(int j=Head[u]; j!=-; j=e[j].next)
{
v = e[j].v;
if(!dfn[v])
{
Tarjan(v, u);
low[u] = min(low[u], low[v]);
}
else if(v!=fa)
low[u] = min(low[u], dfn[v]);
}
} void Slove()
{
int sum=, bnt=;
bool Cut[N]= {false}; Tarjan(, ); for(int i=; i<=n; i++)
{
int v = father[i];
if(v==)
sum++;
else if(dfn[v]<=low[i])
Cut[v] = true;
} for(int i=; i<=n; i++)
{
if(Cut[i])
bnt ++;
} if(sum>)
bnt ++; printf("%d\n", bnt);
} int main()
{
while(scanf("%d", &n), n)
{
int u, v;
char ch; Init();
while(scanf("%d", &u), u)
{
while()
{
scanf("%d%c", &v, &ch);
Add(u, v);
Add(v, u);
if(ch=='\n')
break;
}
} Slove();
}
return ;
}
上一篇:UVA315:Network(求割点)


下一篇:C++中三种传递参数方法的效率分析