解題報告請看 hi.baidu.com/fatboy_cw,貌似這個blog就沒寫多少東西OpenWings就解散了,哀悼...
1
/**//*
2
* Author: fatboy_cw
3 * Created Time: 2010/10/25 20:34:35
4 * File Name: G.cpp
5
*/
6
#include <iostream>
7#include <cstdio>
8#include <cstring>
9#include <cmath>
10#include <cstdlib>
11#include <algorithm>
12#include <vector>
13#include <stack>
14#include <set>
15#include <map>
16using namespace std;
17#define SZ(v) ((int)(v).size())
18
19const int maxn = 30000;
20const int maxm = 300000;
21
22int N,M,Q,Time,bic,low[maxn+5],dfn[maxn+5],edge_bic[maxm+5],b_set[maxn+5],deep[maxn+5],checked[maxn+5];
23stack<int> S;
24set<int> Bic[maxn+5];
25set<int> node_bic[maxn+5];
26map< pair<int,int>,int > ans;
27bool vis[maxn+5];
28struct Adj
{
29 int v,edge;
30
Adj(){}
31 Adj(int _v,int _edge):v(_v),edge(_edge){}
32};
33
34struct Edge{
35 int u,v;
36}edge[maxm+5];
37
38struct Query{
39 int x,y;
40}query[maxn+5];
41
42vector<Adj> adj[maxn+5];
43vector<int> _adj[maxn+5];
44vector<int> q[maxn+5];
45
46void dfs(int u,int b){
47 dfn[u]=low[u]=++Time;
48 for(int i=0;i<adj[u].size();i++){
49 int node=adj[u][i].v;
50 if(!dfn[node]){
51 S.push(adj[u][i].edge);
52 dfs(node,adj[u][i].edge);
53 low[u]=min(low[u],low[node]);
54 if(low[node]>=dfn[u]){
55 bic++;
56 Bic[bic].clear();
57 int e=adj[u][i].edge;
58 while(S.top()!=e && !S.empty()){
59 Bic[bic].insert(S.top());
60 node_bic[edge[S.top()].u].insert(bic);
61 node_bic[edge[S.top()].v].insert(bic);
62 S.pop();
63
}
64 Bic[bic].insert(S.top());
65 node_bic[edge[S.top()].u].insert(bic);
66 node_bic[edge[S.top()].v].insert(bic);
67 S.pop();
68 }
69 }
70 else if(adj[u][i].edge!=b){
71 if(dfn[node]<dfn[u]){
72 S.push(adj[u][i].edge);
73 }
74 low[u]=min(low[u],dfn[node]);
75 }
76 }
77}
78
79int find(int u){
80 if(b_set[u]==u) return u;
81 return b_set[u]=find(b_set[u]);
82}
83
84void findans(int u,int dep){
85 b_set[u]=u;
86 deep[u]=dep;
87 vis[u]=true;
88 for(int i=0;i<_adj[u].size();i++){
89 int node=_adj[u][i];
90 if(vis[node]) continue;
91 findans(node,dep+1);
92 b_set[node]=u;
93 }
94 checked[u]=Time;
95 for(int i=0;i<q[u].size();i++){
96 int node=q[u][i];
97 if(checked[node]==Time){
98 int father=find(node);
99 ans[make_pair(u,node)]=deep[node]-deep[father]+deep[u]-deep[father];
100 }
101 }
102}
103
104int main() {
105 while(scanf("%d%d",&N,&M)!=EOF){
106 if(N+M==0) break;
107 for(int i=1;i<=N;i++) adj[i].clear();
108 for(int i=1;i<=M;i++){
109 scanf("%d%d",&edge[i].u,&edge[i].v);
110 adj[edge[i].u].push_back(Adj(edge[i].v,i));
111 adj[edge[i].v].push_back(Adj(edge[i].u,i));
112 }
113 memset(low,0,sizeof(low));
114 memset(dfn,0,sizeof(dfn));
115 Time=0;
116 bic=0;
117 S=stack<int>();
118 for(int i=1;i<=N;i++) node_bic[i].clear();
119 for(int i=1;i<=N;i++){
120 if(!dfn[i]){
121 dfs(i,0);
122 }
123 }
124 for(int i=1;i<=bic;i++){
125 for(set<int>::iterator it=Bic[i].begin();it!=Bic[i].end();it++){
126 edge_bic[*it]=i;
127 }
128 }
129 for(int i=1;i<=N+bic;i++) _adj[i].clear();
130 for(int i=1;i<=N;i++){
131 if(node_bic[i].size()>1){
132 ++bic;
133 for(set<int>::iterator j=node_bic[i].begin();j!=node_bic[i].end();j++){
134 _adj[*j].push_back(bic);
135 _adj[bic].push_back(*j);
136
137 }
138 }
139 }
140
141 for(int i=1;i<=bic;i++) q[i].clear();
142 scanf("%d",&Q);
143 for(int i=1;i<=Q;i++){
144 scanf("%d%d",&query[i].x,&query[i].y);
145 if(edge_bic[query[i].x]==edge_bic[query[i].y]) continue;
146 q[edge_bic[query[i].x]].push_back(edge_bic[query[i].y]);
147 q[edge_bic[query[i].y]].push_back(edge_bic[query[i].x]);
148 }
149 memset(vis,0,sizeof(vis));
150 memset(checked,0,sizeof(checked));
151 Time=0;
152 ans.clear();
153 memset(deep,0,sizeof(deep));
154 for(int i=1;i<=bic;i++){
155 if(!vis[i]){
156 ++Time;
157 findans(i,0);
158 }
159 }
160 for(int i=1;i<=Q;i++){
161 int x=edge_bic[query[i].x],y=edge_bic[query[i].y];
162 if(x==y){
163 printf("0\n");
164 }
165 else{
166 if(ans.find(make_pair(x,y))!=ans.end()){
167 printf("%d\n",ans[make_pair(x,y)]/2);
168 }
169 else{
170 printf("%d\n",ans[make_pair(y,x)]/2);
171 }
172 }
173 }
174 }
175 return 0;
176}
177
178
posted on 2010-10-29 10:53
OpenWings 閱讀(470)
評論(5) 編輯 收藏 引用