双连通分量
题意：输入比较恶心，没有说有多少点，点的标号也不一定，只给出了边。一个无向图，但是保证是连通的（所以只要做一次dfs），问那些电脑坏了，会使整个网络断开分成几个部分。其实很直白就是求割点。输出就是，如果整个图为点双连通分量，则输出No SPF nodes ， 否则按标号从小到大输出每个割点，并且输出，去掉该点后，整个图会分成几个部分
这题算是个模板题，但是WA了，是因为模板有问题，也是自己对双连通分量的理解有问题，改了一下模板过了，发现自己之前想的东西有点复杂，把模板一些细节处搞错了，但是之前做了几道题都是1Y的，这个题目错了，感觉错得很值。
对于什么是割点，在这里不说了，百度很多，对照着定义，仔细读一下这个代码的话，很容易理解的。
这个模板只是求出了割点，但是没有求出具体每个点双连通分量有哪些点（要用到栈）。
代码中的cut[i]表示点i做了几次割点（一个点可能属于多个点双连通分量），但是要cut[i] + 1才是它把整个图分成了几块，这个是很容易理解的，这里不详说
觉得还要再做很多题，把模板搞好，边双连通分量，点双连通分量一定要搞清楚
#include#include #include #include using namespace std;#define N 1010#define M 100010int Min,Max,tot,rts;int head[N],dfn[N],low[N],cut[N],dcnt; //记得改为vis写法试试struct edge{ int u,v,next;}e[2*M];void add(int u ,int v){ e[tot].u = u; e[tot].v = v; e[tot].next = head[u]; head[u] = tot++; u = u^v; v = u^v; u = u^v; e[tot].u = u; e[tot].v = v; e[tot].next = head[u]; head[u] = tot++;}void dfs(int u ,int fa){ dfn[u] = low[u] = ++dcnt; for(int k=head[u]; k!=-1; k=e[k].next) { int v = e[k].v; if(v == fa) continue; if(!dfn[v]) { dfs(v,u); low[u] = min(low[u] , low[v]); if(fa == -1) { rts++; continue; } if(dfn[u] <= low[v]) cut[u]++; } else low[u] = min(low[u] , dfn[v]); }}void solve(){ int rt; dcnt = rts = 0; memset(dfn,0,sizeof(dfn)); memset(cut,0,sizeof(cut)); rt = Min; dfs(rt,-1); cut[rt] = rts - 1; int ok = 0; for(int i = Min; i<=Max; i++) if(cut[i]) { ok = 1; printf(" SPF node %d leaves %d subnets\n",i,cut[i]+1); } if(!ok) printf(" No SPF nodes\n");}int main(){ int cas = 0; while(true) { int u,v; tot = 0; memset(head,-1,sizeof(head)); cin >> u; if(!u) break; cin >> v; Min = min(u,v); Max = max(u,v); add(u,v); while(cin >> u && u) { cin >> v; add(u,v); Min = min(Min,u); Min = min(Min,v); Max = max(Max,u); Max = max(Max,v); } printf("Network #%d\n",++cas); solve(); cout << endl; } return 0;}