ae模板素材网站,根据颜色找网站,自己做的网站可以挂在哪里,别人怎么看见我做的网站题意#xff1a;
存在n个电话公司的网络连接站点#xff0c;每个站点之间相互连通#xff0c;是一个连通图#xff0c;问#xff0c;如果去掉一个站点#xff0c;能够将整个网络体系变得不再连通#xff0c;那么这样的点有几个#xff0c;即求它的割点个数。
题目
存在n个电话公司的网络连接站点每个站点之间相互连通是一个连通图问如果去掉一个站点能够将整个网络体系变得不再连通那么这样的点有几个即求它的割点个数。
题目
A Telephone Line Company (TLC) is establishing a new telephone cable network. They are connecting several places numbered by integers from 1 to N. No two places have the same number. The lines are bidirectional and always connect together two places and in each place the lines end in a telephone exchange. There is one telephone exchange in each place. From each place it is possible to reach through lines every other place, however it need not be a direct connection, it can go through several exchanges. From time to time the power supply fails at a place and then the exchange does not operate. The officials from TLC realized that in such a case it can happen that besides the fact that the place with the failure is unreachable, this can also cause that some other places cannot connect to each other. In such a case we will say the place (where the failure occured) is critical. Now the officials are trying to write a program for finding the number of all such critical places. Help them.
Input
The input file consists of several blocks of lines. Each block describes one network. In the first line of each block there is the number of places N 100. Each of the next at most N lines contains the number of a place followed by the numbers of some places to which there is a direct line from this place. These at most N lines completely describe the network, i.e., each direct connection of two places in the network is contained at least in one row. All numbers in one line are separated by one space. Each block ends with a line containing just ‘0’. The last block has only one line with N 0.
Output
The output contains for each block except the last in the input file one line containing the number of critical places.
Sample Input
5 5 1 2 3 4 0 6 2 1 3 5 4 6 2 0 0
Sample Output
1 2
分析
无向图中如果有一个顶点删除这个顶点以及这个顶点相关联的边以后图的连通分量增多就称这个点集为割点。 判断一个顶点是不是割点除了从定义还可以从DFS深度优先遍历的角度出发。我们先通过DFS定义两个概念。 假设DFS中我们从顶点U访问到了顶点V此时顶点V还未被访问过那么我们称顶点U为顶点V的父顶点V为U的孩子顶点。 在顶点U之前被访问过的顶点我们就称之为U的祖先顶点。 显然如果顶点U的所有孩子顶点可以不通过父顶点U而访问到U的祖先顶点那么说明此时去掉顶点U不影响图的连通性U就不是割点。 相反如果顶点U至少存在一个孩子顶点必须通过父顶点U才能访问到U的祖先顶点那么去掉顶点U后顶点U的祖先顶点和孩子顶点就不连通了说明U是一个割点。 情况11.u为当前搜索树的根结点且u的子树数量大于1 即 (xfson2) 情况22.u不为根且存在树边(u,v)使dfn(u)low(v) 对应(low[v] dfn[x] x ! f)
AC代码
#include stdio.h
#include string.h
#include algorithm
using namespace std;
const int N 1e310;
const int M 1e610;
struct node
{int v,next;int u;
} s[M];
int ans ;
int n,a,b;
int dp[N];
int top,num;
int dfn[N],low[N];
int cut[N];//标记是否为割点
int id;
void tarjan(int x,int f) //当前结点以及父节点
{low[x] dfn[x] id; //(1)结点u初值int son 0; //定义根结点孩子个数for(int i dp[x]; ~i; i s[i].next)//(2)枚举每一条边{int v s[i].v;//(3)入过结点u为强连通分量的根节点时if(!dfn[v]) //(4)没有被访问时候递归搜索{tarjan(v,x);low[x] min(low[x],low[v]);if(low[v] dfn[x] x ! f) //(5)如果该子节点不能到达祖先节点 (标记)cut[x] 1;if(x f)//每从根结点往孩子走就加1son;}low[x] min(low[x],dfn[v]);}if(x f son 2) //(6)根节点且孩子个数大于2即为割点cut[x] 1;
}
void add(int u,int v)
{s[top].v v;s[top].next dp[u];dp[u] top;
}
void init()
{memset(dp,-1,sizeof(dp));memset(cut,0,sizeof(cut));memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));id ans top 0;
}
int main()
{while(~scanf(%d,n) n){init();while(scanf(%d,a) a){char ch;while(scanf(%d%c,b,ch)){add(a,b),add(b,a);if(ch \n)break;}}for(int i 1; in; i){if(!dfn[i])tarjan(i,i);}for(int i 1; in; i){if(cut[i])ans;}printf(%d\n,ans);}return 0;
}
