撰写问题描述
抗日战争时期，冀中平原的地道战曾发挥重要作用。
地道的多个站点间有通道连接，形成了庞大的网络。但也有隐患，当敌人发现了某个站点后，其它站点间可能因此会失去联系。
我们来定义一个危险系数DF(x,y)：
对于两个站点x和y (x != y), 如果能找到一个站点z，当z被敌人破坏后，x和y不连通，那么我们称z为关于x,y的关键点。相应的，对于任意一对站点x和y，危险系数DF(x,y)就表示为这两点之间的关键点个数。
本题的任务是：已知网络结构，求两站点之间的危险系数。
输入格式
输入数据第一行包含2个整数n(2 <= n <= 1000), m(0 <= m <= 2000),分别代表站点数，通道数；
接下来m行，每行两个整数 u,v (1 <= u, v <= n; u != v)代表一条通道；
最后1行，两个数u,v，代表询问两点之间的危险系数DF(u, v)。
输出格式
一个整数，如果询问的两点不连通则输出-1.
样例输入
7 6
1 3
2 3
3 4
3 5
4 5
5 6
1 6
1 3
2 3
3 4
3 5
4 5
5 6
1 6
样例输出
2
- 题解
- dfs求出st到ed所有路径上的点出现的次数
- 其中出现次数与st、ed出现次数相同的点即为割点
- 直接用一个数组纪录路径，每次到达ed进行一次统计
- 代码
-
#include<algorithm> #include <iostream> #include <fstream> #include <cstdlib> #include <cstring> #include <cassert> #include <cstdio> #include <vector> #include <string> #include <cmath> #include <queue> #include <stack> #include <set> #include <map> using namespace std; #define P(a,b,c) make_pair(a,make_pair(b,c)) #define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,a,n) for (int i=n;i>=a;i--) #define CLR(vis) memset(vis,0,sizeof(vis)) #define MST(vis,pos) memset(vis,pos,sizeof(vis)) #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef pair<int,pair<int,int> >pii; typedef long long ll; typedef unsigned long long ull; const ll mod = 1000000007; const int INF = 0x3f3f3f3f; ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; } template<class T>inline void gmax(T &A, T B) { (A<B)&&(A=B);//if(B>A)A=B; } template<class T>inline void gmin(T &A, T B) { (A>B)&&(A=B);//if(B<A)A=B; } template <class T> inline bool scan(T &ret) { char c; int sgn; if(c=getchar(),c==EOF) return 0; //EOF while(c!='-'&&(c<'0'||c>'9')) c=getchar(); sgn=(c=='-')?-1:1; ret=(c=='-')?0:(c-'0'); while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn; return 1; } inline void outt(int x) { if(x>9) outt(x/10); putchar(x%10+'0'); } const int maxn=1e6+10; struct Edge{ int v; int w; }edge[maxn*2]; int nxt[maxn]; int head[maxn]; int tot=0; void addedge(int u,int v,int w){ edge[++tot].v=v; edge[tot].w=w; nxt[tot]=head[u]; head[u]=tot; } int cnt[maxn]; int road[maxn]; bool vis[maxn]; int st,ed; void dfs(int u,int step){ road[step]=u; if(u==ed){ rep(i,1,step){ cnt[road[i]]++; } return ; } vis[u]=1; for(int i=head[u];i;i=nxt[i]){ if(!vis[edge[i].v]){ dfs(edge[i].v,step+1); } } vis[u]=0; } int main(){ int n,m; cin>>n>>m; while(m--){ int u,v; cin>>u>>v; addedge(u,v,1); addedge(v,u,1); } cin>>st>>ed; dfs(st,1); if(cnt[ed]==0){ puts("-1"); return 0; } tot=0; rep(i,1,n){ if(cnt[i]==cnt[ed]&&i!=ed&&i!=st){ tot++; } } cout<<tot<<endl; return 0; }
-