posts - 5,  comments - 5,  trackbacks - 0

解题报告请看 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()!=&& !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 阅读(402) 评论(5)  编辑 收藏 引用

FeedBack:
# re: 杭州G题的代码
2011-04-04 22:29 | 此最相思
缩点以后怎么处理 能说的详细些么? 希望能举个具体例子说说 谢谢  回复  更多评论
  
# re: 杭州G题的代码
2011-04-04 22:31 | OpenWings
@此最相思
对无向图收缩点双连通分量以后,把每个分量连接到对应割点上,对于询问用tarjan处理lca(rmq貌似还得加个虚根),然后用距离除2即可。
  回复  更多评论
  
# re: 杭州G题的代码
2011-04-10 11:02 | 此最相思
@OpenWings
这题是不是求经过几个连通分量?  回复  更多评论
  
# re: 杭州G题的代码
2011-04-10 18:54 | 此最相思
您有QQ么 在线请教一下 您的代码我好几个没看懂...
  回复  更多评论
  
# re: 杭州G题的代码
2011-04-11 20:34 | fatboy_cw
@此最相思
271763295,最近事情有点多回复晚了不好意思  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年4月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

常用链接

留言簿(1)

随笔分类

随笔档案

队员

最新评论

  • 1. re: 杭州G题的代码
  • @此最相思
    271763295,最近事情有点多回复晚了不好意思
  • --fatboy_cw
  • 2. re: 杭州G题的代码
  • 您有QQ么 在线请教一下 您的代码我好几个没看懂...
  • --此最相思
  • 3. re: 杭州G题的代码
  • @OpenWings
    这题是不是求经过几个连通分量?
  • --此最相思
  • 4. re: 杭州G题的代码
  • @此最相思
    对无向图收缩点双连通分量以后,把每个分量连接到对应割点上,对于询问用tarjan处理lca(rmq貌似还得加个虚根),然后用距离除2即可。
  • --OpenWings
  • 5. re: 杭州G题的代码
  • 缩点以后怎么处理 能说的详细些么? 希望能举个具体例子说说 谢谢
  • --此最相思

阅读排行榜

评论排行榜