Codeforces Round #143 (Div. 二) E. Cactus(LCA+无向图缩点)
题意:
无向图中的任意一点只属于一个简单环,然后询问任何两点间有多少条不同的简单路。
一般简单路的定义是一条无重复边和不经过重复点的路径,题述的定义是:可以经过重复点但无重复边的路径,所以这种定义性问题还是仔细读读题。
思路:由此图的特殊性可知,缩点成树以后,路径每经过一个缩点,就会有两种不同的选择,所以可以lca求任何两个节点间的缩点个数
此图的特殊性缩点很简单,dfs一下就可以了,但是一般的无向图的缩点需要tarjan算法,自己的无向图缩点模版是:
int dfn[N],sta[N],top,scc,index,col[N],low[N];
void tarjan(int u,int pa)
{
dfn[u] = low[u] = ++index;
sta[++top] = u;
for(int i = head[u];~i;i = es[i].nxt)
{
int v = es[i].v;
if(v == pa) continue;
if(dfn[v] == 0)
{
tarjan(v,u);
low[u] = min(low[u],low[v]);
if(low[v] > dfn[u])
{
++scc;
int vv;
do
{
vv = sta[top--];
col[vv] = scc;
}while(vv != v);
}
}
else low[u] = min(low[u],dfn[v]);
}
}
scc++;
while(top) col[sta[top--]] = scc; //栈中剩余的双连通分量别漏了
#include <iostream> #include <cstring> #include <cmath> #include <queue> #include <stack> #include <list> #include <map> #include <set> #include <sstream> #include <string> #include <vector> #include <cstdio> #include <ctime> #include <bitset> #include <algorithm> #define SZ(x) ((int)(x).size()) #define ALL(v) (v).begin(), (v).end() #define foreach(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++ i) #define REP(i,n) for ( int i=1; i<=int(n); i++ ) using namespace std; typedef long long ll; #define X first #define Y second typedef pair<ll,ll> pii; int n,m; const int N = 1e5+100; struct Edge{ int v,nxt; Edge(){} Edge(int v,int nxt):v(v),nxt(nxt){}; }es[N*2],es2[N*2]; int ecnt,ecnt2; int head[N],head2[N]; inline void add_edge(int u,int v){ es[++ecnt] = Edge(v,head[u]); head[u] = ecnt; es[++ecnt] = Edge(u,head[v]); head[v] = ecnt; } bool is_scc[N]; int dfn[N],sta[N],top,scc,index,col[N],low[N]; void tarjan(int u,int pa) { dfn[u] = low[u] = ++index; sta[++top] = u; for(int i = head[u];~i;i = es[i].nxt) { int v = es[i].v; if(v == pa) continue; if(dfn[v] == 0) { tarjan(v,u); low[u] = min(low[u],low[v]); if(low[v] > dfn[u]) { ++scc; int vv; do { vv = sta[top--]; col[vv] = scc; }while(vv != v); } } else low[u] = min(low[u],dfn[v]); } } int dp[N]; int dep[N]; bool vis[N]; int pa[N][20]; void bfs() { queue<int>q; q.push(1); pa[1][0] = 1; vis[1] = 1; dp[1] = is_scc[1]; while(!q.empty()) { int u = q.front(); q.pop(); for(int i = 1;i < 20; i++) pa[u][i] = pa[pa[u][i-1]][i-1]; for(int i = head2[u];~i;i = es2[i].nxt) { int v = es2[i].v; if(vis[v] == 0) { vis[v] = 1; dp[v] = dp[u]+is_scc[v]; pa[v][0] = u; dep[v] = dep[u]+1; q.push(v); } } } } int LCA(int u,int v) { if(dep[u]>dep[v]) swap(u,v); for(int det=dep[v]-dep[u],i=0;det;i++,det>>=1) if(det&1) v=pa[v][i]; if(v==u) return v; for(int i=20-1;i>=0;i--) if(pa[u][i]!=pa[v][i]) v=pa[v][i],u=pa[u][i]; return pa[u][0]; } int pw[N]; const int MOD = 1e9+7; int main(){ memset(head,-1,sizeof(head)); memset(head2,-1,sizeof(head2)); pw[0] = 1; REP(i,N-10) pw[i] = pw[i-1]*2%MOD; cin>>n>>m; REP(i,m){ int u,v; scanf("%d%d",&u,&v); add_edge(u,v); } REP(i,n) if(dfn[i] == 0) tarjan(i,-1); scc++; while(top) col[sta[top--]] = scc; REP(u,n){ for(int i = head[u];~i;i = es[i].nxt){ int v = es[i].v; if(col[u] == col[v]) { is_scc[col[u]] = 1; continue; } es2[++ecnt2] = Edge(col[v],head2[col[u]]); head2[col[u]] = ecnt2; } } bfs(); int Q; cin>>Q; REP(i,Q){ int u,v; scanf("%d%d",&u,&v); u = col[u],v = col[v]; int lca = LCA(u,v); int cnt = dp[u]+dp[v]-2*dp[lca]+is_scc[lca]; printf("%d\n",pw[cnt]); } }
版权声明:本文为博主原创文章,未经博主允许不得转载。