<题目链接>
题目大意：
给你一个连通的无向图，问你其中割点的编号，并且输出删除该割点后，原图会被分成几个连通分量。
解题分析：
Tarjan求割点模板题。
1 #include <cstring> 2 #include <cstdio> 3 #include <algorithm> 4 using namespace std; 5 6 #define rep(i,s,t) for(int i=s;i<=t;i++) 7 #define clr(i,a) memset(i,a,sizeof(i)) 8 const int N = 2005; 9 int head[N], cnt, rt, add_block[N], dfn[N], low[N], fa[N], tot; 10 struct Edge{ 11 int to, next; 12 }e[N*N]; 13 inline int read(){ 14 int r=0, f=1; char c=getchar(); 15 for(; c<'0'||c>'9'; c=getchar()) if(c=='-')f=-1; 16 for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; 17 return f*r; 18 } 19 void add(int u, int v) { 20 e[++cnt].next=head[u]; head[u]=cnt; e[cnt].to=v; 21 e[++cnt].next=head[v]; head[v]=cnt; e[cnt].to=u; 22 } 23 void tarjan(int u, int fa) { 24 dfn[u]=low[u]=++tot; 25 int child=0; 26 for(int i=head[u];~i; i=e[i].next) { 27 int v=e[i].to; 28 if(!dfn[v]) { 29 tarjan(v, u); 30 ++child; 31 if(low[v]>=dfn[u])++add_block[u]; //add_block代表删除u后能够增加的分量个数 32 low[u]=min(low[v], low[u]); 33 } 34 else if(dfn[v]<dfn[u] && fa!=v)low[u]=min(low[u], dfn[v]); 35 } 36 if(child==1 && fa==-1) add_block[u]=0; //如果 37 else if(child>1 && fa==-1) add_block[u]=child-1; 38 } 39 40 int main() { 41 int u, v, ncase=0; 42 while(true) { 43 u=read(); if(u==0) break; 44 v=read(); 45 clr(head, -1); clr(add_block, 0); cnt=tot=0; clr(dfn, 0); clr(low, 0); 46 add(u, v);rt=max(rt, v); 47 while(1) { 48 u=read(); if(u==0) break; 49 v=read(); 50 add(u, v); rt=max(rt, v); //rt用来记录序号最大的节点 51 } 52 rep(i, 1, rt) if(head[i]!=-1 && !dfn[i]) tarjan(i, -1); 53 int flag=0; 54 printf("Network #%d ", ++ncase); 55 rep(i, 1, rt) if(add_block[i]) 56 printf(" SPF node %d leaves %d subnets ", i, add_block[i]+1), flag=1; 57 if(!flag) puts(" No SPF nodes"); 58 puts(""); 59 } 60 return 0; 61 }
2018-12-02