做完Mining Your Own Business后觉得这个题没什么意思了,数据范围小的连边数不清空都能A。
题解直接看这篇吧。做题的经历也挺……对吧。
#include<iostream> #include<algorithm> #include<cmath> #include<cstring> #include<cstdio> #include<vector> #include<queue> #include<stack> #include<set> #include<map> using namespace std; int read(){ int sum=0,f=1;char x=getchar(); while(x<'0'||x>'9'){ if(x=='-') f=-1; x=getchar(); }while(x>='0'&&x<='9'){ sum=sum*10+x-'0'; x=getchar(); }return sum*f; } struct EDGE{ int ed,nex; }edge[3000];int num,first[600]; int n,m,time_,top,root; int dfn[600],low[600],sta[40000]; vector<int>vcc[600]; int vccnum,T; long long ans1,ans2; bool cut[600]; void add(int st,int ed){ edge[++num].ed=ed; edge[num].nex=first[st]; first[st]=num; } void init(){ memset(edge,0,sizeof(edge)); memset(first,0,sizeof(first)); num=n=time_=top=root=0; memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); for(int i=1;i<=vccnum;i++) vcc[i].clear(); vccnum=0; memset(cut,0,sizeof(cut)); ans1=0; ans2=1; } void tarjan(int x){ dfn[x]=low[x]=++time_; sta[++top]=x; if(x==root&&first[x]==0){ vcc[++vccnum].push_back(x); return; } int child=0; for(int i=first[x];i;i=edge[i].nex){ int y=edge[i].ed; if(!dfn[y]){ tarjan(y); low[x]=min(low[x],low[y]); if(low[y]>=dfn[x]){ child++; if((x==root&&child>=2)||(x!=root&&child>0)) cut[x]=1; vcc[++vccnum].push_back(x); int p; do{ p=sta[top--]; vcc[vccnum].push_back(p); }while(p!=y); } }else low[x]=min(low[x],dfn[y]); } } int main(){ while(++T){ m=read(); if(m==0) return 0; init(); for(int i=1,x,y;i<=m;i++){ x=read();y=read(); add(x,y);add(y,x); n=max(n,x);n=max(n,y); } // cout<<"m="<<m<<" n="<<n<<endl; for(int i=1;i<=n;i++) if(!dfn[i]) root=i,tarjan(i); for(int i=1;i<=vccnum;i++){ int sum=0; for(int j=0;j<vcc[i].size();j++) if(cut[vcc[i][j]]) sum++; if(!sum){ ans1+=2; ans2=ans2*((vcc[i].size()-1)*vcc[i].size())/2; }else if(sum==1){ ans1++; ans2=ans2*(vcc[i].size()-1); } } printf("Case %d: %lld %lld\n",T,ans1,ans2); }return 0; }View Code
最后还是听从内心又码了一遍。