| Time Limit: 5000MS | Memory Limit: 65536K | |
| Total Submissions: 5459 | Accepted: 1788 |
当m==0 时，特判输出 n-1~~~
先求出原始的连通分量，
然后只有删割点才会增加连通分量，枚举每个割点
最后加上原始的
1 #include2 #include 3 #include 4 5 using namespace std; 6 7 const int N(100015); 8 int n,m,u,v; 9 int sumedge,head[N<<1]; 10 struct Edge 11 { 12 int to,next; 13 Edge(int to=0,int next=0) : 14 to(to),next(next) {} 15 }edge[N*5]; 16 17 void ins(int from,int to) 18 { 19 edge[++sumedge]=Edge(to,head[from]); 20 head[from]=sumedge; 21 } 22 23 int low[N<<1],dfn[N<<1],tim; 24 int sumcol,num[N]; 25 int cutpoint[N]; 26 27 void DFS(int now,int pre) 28 { 29 low[now]=dfn[now]=++tim; 30 int sumtredge=0,if_cutpoint=0; 31 for(int i=head[now];i!=-1;i=edge[i].next) 32 { 33 int go=edge[i].to; 34 if((i^1)!=pre) 35 { 36 if(!dfn[go]) 37 { 38 sumtredge++; 39 DFS(go,i); 40 if(low[go]>=dfn[now]) 41 { 42 if_cutpoint=1; 43 num[now]++; 44 } 45 46 low[now]=min(low[now],low[go]); 47 } 48 else low[now]=min(low[now],dfn[go]); 49 } 50 } 51 if(pre==-1) 52 { 53 if(sumtredge>1) cutpoint[now]=1; 54 } 55 else if(if_cutpoint) cutpoint[now]=1; 56 } 57 58 int ans,cnt,tmp,vis[N],root[N],cut[N]; 59 60 void link(int x) 61 { 62 vis[x]=1; 63 for(int i=head[x];i!=-1;i=edge[i].next) 64 { 65 v=edge[i].to; 66 if(!vis[v]) link(v); 67 } 68 } 69 70 void cut_point(int pre,int fa) 71 { 72 vis[pre]=1; 73 for(int i=head[pre];i!=-1;i=edge[i].next) 74 { 75 int go=edge[i].to; 76 if(!vis[go]) 77 { 78 if(pre==fa) cnt++; 79 cut_point(go,fa); 80 } 81 } 82 } 83 84 void init(int n) 85 { 86 sumedge=-1; ans=tim=tmp=cnt=0; 87 memset(vis,0,sizeof(vis)); 88 memset(low,0,sizeof(low)); 89 memset(dfn,0,sizeof(dfn)); 90 memset(num,0,sizeof(num)); 91 memset(cut,0,sizeof(cut)); 92 memset(root,0,sizeof(root)); 93 memset(head,-1,sizeof(head)); 94 memset(cutpoint,0,sizeof(cutpoint)); 95 } 96 97 int main() 98 { 99 // freopen("makerout.txt","r",stdin);100 // freopen("myout.txt","w",stdout);101 102 while(~scanf("%d%d",&n,&m)&&n)103 {104 init(n);105 if(m==0) printf("%d\n",n-1);106 else107 {108 for(;m;m--) 109 {110 scanf("%d%d",&u,&v);111 ins(u,v); ins(v,u);112 }113 for(int i=0;i