Railway
题意：一个无向图，1求不在任何一个环里的边数；2求在不止一个环里的边数。
第一问明显就是求桥，第二问，如果求出的某个点双连通分量里面边数多于点数，说明不止一个环，那么所有的边都在不止一个环里。
该求点双连通的，，求成了边双连通。。。要仔细分析问题。
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 const int maxv=10010; 7 int n,m; 8 int ans1,ans2; 9 struct Edge{10 int u,v,nex;11 bool iscut;12 }e[100010<<1];13 int head[maxv];14 int cnt;15 void init(){16 memset(head,-1,sizeof(head));17 cnt=0;18 }19 void add(int u,int v){20 e[cnt].u=u;21 e[cnt].iscut=0;22 e[cnt].v=v;23 e[cnt].nex=head[u];24 head[u]=cnt++;25 }26 int pre[maxv],bccno[maxv],dfsk,bcc_cnt;27 int vis[maxv];28 vector bcc[maxv];29 30 int dfs(int u,int id){31 int lowu=pre[u]=++dfsk;32 for(int i=head[u];i!=-1;i=e[i].nex){33 int v=e[i].v;34 if(i==(id^1)) continue;35 if(!pre[v]){36 int lowv=dfs(v,i);37 lowu=min(lowu,lowv);38 if(lowv>pre[u]) e[i].iscut=e[i^1].iscut=1,ans1++;39 }40 else lowu=min(lowu,pre[v]);41 }42 return lowu;43 }44 void dfs1(int u){45 bccno[u]=bcc_cnt;46 vis[u]=1;47 for(int i=head[u];i!=-1;i=e[i].nex){48 if(e[i].iscut) continue;49 bcc[bcc_cnt].push_back(i);50 int v=e[i].v;51 if(!vis[v]) dfs1(v);52 }53 }54 55 void find_bcc(int n){56 memset(pre,0,sizeof(pre));57 memset(vis,0,sizeof(vis));58 memset(bccno,0,sizeof(bccno));59 dfsk=bcc_cnt=0;60 for(int i=0;i
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 const int maxv=10010; 8 int n,m; 9 int ans1,ans2; 10 struct Edge 11 { 12 int u,v,nex; 13 }e[100010<<1]; 14 int head[maxv]; 15 int cnt; 16 void init() 17 { 18 memset(head,-1,sizeof(head)); 19 cnt=0; 20 } 21 void add(int u,int v) 22 { 23 e[cnt].u=u; 24 e[cnt].v=v; 25 e[cnt].nex=head[u]; 26 head[u]=cnt++; 27 } 28 int pre[maxv],bccno[maxv],dfsk,bcc_cnt; 29 stack s; //存的是边的标号 30 vector bcc[maxv]; //存的是边的标号 31 int vis[maxv]; 32 33 int dfs(int u,int id){ 34 int lowu=pre[u]=++dfsk; 35 for(int i=head[u];i!=-1;i=e[i].nex){ 36 int v=e[i].v; 37 if(i==(id^1)) continue; 38 if(!pre[v]){ 39 s.push(i); 40 int lowv=dfs(v,i); 41 lowu=min(lowu,lowv); 42 if(lowv>pre[u]) ans1++; //割边 43 if(lowv>=pre[u]){ 44 bcc_cnt++; 45 bcc[bcc_cnt].clear(); 46 for(;;){ 47 int p=s.top(); 48 s.pop(); 49 bcc[bcc_cnt].push_back(p); 50 if(p==i) break; 51 } 52 } 53 } 54 else if(pre[v]