其实题目的数据不够规范,因为它的点可能不连续,而且数据里面一定有根节点1,这个在题目里体现不了!
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<stack> using namespace std; #define N 1005 vector<int> vec[N]; int step,low[N],dfn[N],blg[N]; void add(int x,int y) { vec[x].push_back(y); vec[y].push_back(x); } void tarjan(int now) { low[now]=dfn[now]=step++; int len=vec[now].size(); for(int i=0;i<len;i++) { int u=vec[now][i]; if(dfn[u]==-1) { tarjan(u); if(dfn[now]<=low[u])blg[now]++; //产生一个连通分支 else low[now]=min(low[now],low[u]); } else low[now]=min(low[now],dfn[u]); } } int main() { //freopen("a.txt","r",stdin); int x,ca=1; while(scanf("%d",&x)&&x) { int y; scanf("%d",&y); for(int i=1;i<N;i++)vec[i].clear(); add(x,y); while(scanf("%d",&x)&&x) { scanf("%d",&y); add(x,y); } memset(blg,0,sizeof(blg)); memset(dfn,-1,sizeof(dfn)); step=0; tarjan(1); printf("Network #%d\n",ca++); bool flag=false; for(int i=1;i<N;i++) { if(i!=1)blg[i]++; //加上当前点的父节点的连通数,当这点是根节点时没有父节点,所以不能加1 if(blg[i]<2)continue; flag=true; printf(" SPF node %d leaves %d subnets\n",i,blg[i]); } if(!flag)printf(" No SPF nodes\n"); printf("\n"); } return 0; }