题目链接:Click here~~
题意:
又学了一天。呵呵。
解题思路:
先不写思路了,到时候来个总结。
#include <map> #include <stack> #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int N = 2e3+5; const int M = 1e4+5; struct Vertex { int head; }V[N]; struct Edge { int v,next; }E[M]; int n,top,scc,id,dfn[N],low[N],belong[N],sub[N]; bool ok,in[N],cut_p[N],cut_e[M]; stack<int> S; map<int,int> M1,M2; void init() { top = n = 0; memset(V,-1,sizeof(V)); M1.clear(); M2.clear(); } void add_edge(int u,int v) { if(!M1.count(u)) { M1[u] = n; M2[n++] = u; } u = M1[u]; if(!M1.count(v)) { M1[v] = n; M2[n++] = v; } v = M1[v]; E[top].v = v; E[top].next = V[u].head; V[u].head = top++; } void tarjan(int pre,int u) { dfn[u] = low[u] = ++id; int cnt = 0; //S.push(u); for(int i=V[u].head;~i;i=E[i].next) { int v = E[i].v; if(v == pre) continue; if(!dfn[v]) { ++cnt; tarjan(u,v); low[u] = min(low[u],low[v]); if(u!=pre && dfn[u]<=low[v]) { cut_p[u] = true; sub[u]++; } if(dfn[u] < low[v]) cut_e[i] = true; } else low[u] = min(low[u],dfn[v]); } if(u==pre && cnt>1) { cut_p[u] = true; sub[u] = cnt-1; } } void get_cut() { memset(cut_p,false,sizeof(cut_p)); memset(cut_e,false,sizeof(cut_e)); memset(dfn,0,sizeof(dfn)); memset(sub,0,sizeof(sub)); for(int i=0;i<n;i++) if(!dfn[i]) tarjan(i,i); for(int i=1;i<=1000;i++) { if(!M1.count(i) || sub[ M1[i] ]==0) continue; ok = true; printf(" SPF node %d leaves %d subnets\n",i,sub[ M1[i] ]+1); } } int main() { int u,v,ncase=0; while(~scanf("%d",&u),u) { init(); scanf("%d",&v); add_edge(u,v); add_edge(v,u); while(~scanf("%d",&u),u) { scanf("%d",&v); add_edge(u,v); add_edge(v,u); } if(ncase) puts(""); printf("Network #%d\n",++ncase); ok = false; get_cut(); if(!ok) puts(" No SPF nodes"); } return 0; }