这道题的输入异常鬼畜。= =无法直视
题意:给一个图。输出割点以及删掉割点后形成几个连通块
还是忍不住吐槽:异常鬼畜的输入,还有输出,一不注意就PE
还有,注意到这道题的点不是按顺序给定你的。你需要建立一个point数组来存储点。代码如下。= = 套个模板一不小心就WA了。鬼畜的题、
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <set> #include <vector> #include <map> #include <queue> #include <set> #include <algorithm> using namespace std; #define MAXN 1010 vector <int> e[MAXN]; int dfn[MAXN],low[MAXN],pre[MAXN],n,m; bool gedian[MAXN]; int times=0,tot=0; char vis[MAXN]; int point[MAXN]; void tarjan_3(int u){ dfn[u]=low[u]=++times; for(int i=0;i<(int)e[u].size();i++){ int v=e[u][i]; if(!dfn[v]){ pre[v]=u; tarjan_3(v); low[u]=min(low[u],low[v]); } else if(pre[u]!=v){ low[u]=min(low[u],dfn[v]); } } } void solve(){ times=tot=0; memset(dfn,0,sizeof(dfn)); memset(gedian,0,sizeof(gedian)); memset(pre,0,sizeof(pre)); tarjan_3(point[1]); int cnt=0; for(int i=2;i<=point[0];i++){ if(pre[point[i]]==point[1]) cnt++; else if(dfn[pre[point[i]]]<=low[point[i]])gedian[pre[point[i]]]=true; } if(cnt>1)gedian[point[1]]=true;
return ; } void Addpoint(int x){ if(vis[x])return ; vis[x]=1; int &num=point[0]; point[++num]=x; } char vis1[MAXN]; void bfs(int x,int dian){ queue <int> q; q.push(x); vis1[x]=1; while(!q.empty()){ int now=q.front(); q.pop(); for(int i=0;i<(int)e[now].size();i++){ int next=e[now][i]; if(next==dian)continue; if(vis1[next])continue; vis1[next]=1; q.push(next); } } } int main() { int x,y; int cas=0; int ff=1; while(~scanf("%d",&x)){ if(x==0){ if(ff==0)break; printf("Network #%d\n",++cas); puts(" No SPF nodes"); puts(""); ff=x; continue; } scanf("%d",&y); if(y==0)break; for(int i=0;i<MAXN;i++)e[i].clear(); memset(vis,0,sizeof(vis)); point[0]=0; e[x].push_back(y); e[y].push_back(x); Addpoint(x); Addpoint(y); while(~scanf("%d",&x)&&x){ scanf("%d",&y); e[x].push_back(y); e[y].push_back(x); Addpoint(x); Addpoint(y); } ff=x; solve(); int flag=0; printf("Network #%d\n",++cas); for(int i=1;i<=point[0];i++) if(gedian[point[i]]){ int ans=0; memset(vis1,0,sizeof(vis1)); for(int j=1;j<=point[0];j++){ if(point[j]==point[i])continue; if(!vis1[point[j]]){ bfs(point[j],point[i]); ans++; } } printf(" SPF node %d leaves %d subnets\n",point[i],ans); flag=1; } if(!flag){ puts(" No SPF nodes"); } puts(""); } return 0; }
|