强连通 1269 迷宫城堡 2767 Proving Equivalences 3836 Equivalent Sets 1827 Summer Holiday 3072 Intelligence System 3861 The King’s Problem 3639 Hawk-and-Chicken 3594 Cactus 仙人掌图 4685 [双连通]: 2242 考研路茫茫——空调教室 双联通缩点+树形DP 2460 Network 边双连通 3849 By Recognizing These Guys, We Find Social Networks Useful 双连通求桥 3896 Greatest TC 双连通 4005 The war 边双连通 3394 Railway 双连通求块 [LCA]: 2586 How far away ？ 2874 Connections between cities 3078 Network 3830 Checkers 4338 Simple Path
参考Vendetta：
需要补充的是vis可以在访问到节点时就标记，也可以在访问完其子孙后再标记，区别在于前者可以查询a和b的关系以及b和a的关系，而后者只能查询b和a的关系（假设先访问a），但既然是无向图，答案是一样的，目测放前面可能更强大。
HDU2586
#include<cstdio>
#include<cstring>
#include<cstring>
#include<iostream>
int const MAX = 40005;
struct Edge
{
int id, val;
int next;
}e[2 * MAX];
int n, m, cnt;
int x[MAX], y[MAX], z[MAX];
int fa[MAX], dist[MAX], pre[MAX];
bool vis[MAX];
void _add(int u, int v, int w)
{
e[cnt].id = u;
e[cnt].val = w;
e[cnt].next = pre[v];
pre[v] = cnt++;
}
int Find(int x)
{
return x == fa[x] ? x : fa[x] = Find(fa[x]);
}
void tarjan(int k)
{
vis[k]=true;
fa[k]=k;
for(int i=pre[k];i;i=e[i].next){
if(!vis[e[i].id]){
dist[e[i].id]=dist[k]+e[i].val;
tarjan(e[i].id);
fa[e[i].id] = k;
}
}
//vis[k]=true;
for(int i=1;i<=m;i++){
if(x[i]==k&&vis[y[i]])
z[i]=Find(y[i]);
}
}
int main()
{
int T,u,v,w;
scanf("%d",&T);
while(T--){
scanf("%d %d", &n, &m);
cnt=0;
memset(pre,0,sizeof(pre));
for(int i=1;i<n;i++){
scanf("%d %d %d",&u,&v,&w);
_add(u,v,w);
_add(v,u,w);
}
for(int i=1;i<=n;i++)
x[i]=y[i]=z[i]=0;
for(int i=1;i<=m;i++)
scanf("%d %d",&x[i],&y[i]);
memset(vis, false, sizeof(vis));
dist[1] = 0;
tarjan(1);
for(int i = 1; i <= m; i++)
printf("%d
",dist[x[i]] + dist[y[i]] - 2 * dist[z[i]]);
}
}
HDU2874
#include <iostream>
#include <vector>
#include <stack>
#include <cstring>
#include <cstdio>
#include <memory.h>
#include<vector>
using namespace std;
int Laxt[10001],Next[20001],To[20001],Len[20001];
int Laxt2[10001],Next2[2000001],To2[2000001],ans[1000001];
bool vis[10001];
int cnt,cnt2;
int dis[10001],fa[10001];
void _update()
{
memset(Laxt,-1,sizeof(Laxt));
memset(Laxt2,-1,sizeof(Laxt2));
memset(vis,false,sizeof(vis));
cnt=cnt2=0;
}
void _add(int u,int v,int d){
Next[cnt]=Laxt[u];
Laxt[u]=cnt;
To[cnt]=v;
Len[cnt++]=d;
}
void _add2(int u,int v){
Next2[cnt2]=Laxt2[u];
Laxt2[u]=cnt2;
To2[cnt2++]=v;
Next2[cnt2]=Laxt2[v];
Laxt2[v]=cnt2;
To2[cnt2++]=u;
}
int _findfa(int v){
if(v==fa[v]) return fa[v];
return fa[v]=_findfa(fa[v]);
}
void _tarjan(int v)
{
vis[v]=true;fa[v]=v;
for(int i=Laxt[v];i!=-1;i=Next[i]){
if(!vis[To[i]]){
dis[To[i]]=dis[v]+Len[i];
_tarjan(To[i]);
fa[To[i]]=v;
}
}
for(int i=Laxt2[v];i!=-1;i=Next2[i]){
if(vis[To2[i]]){
int tmp=_findfa(To2[i]);
if(dis[To2[i]]!=-1)
ans[i/2]=dis[v]+dis[To2[i]]-2*dis[tmp];
}
}
}
int main()
{
int n,m,c,i,x,y,z;
while(~scanf("%d %d %d",&n,&m,&c)){
_update();
for(i=0;i<m;i++){
scanf("%d%d%d",&x,&y,&z);
_add(x,y,z);
_add(y,x,z);
}
for(i=0;i<c;i++){
scanf("%d%d",&x,&y);
_add2(x,y);
}
for(i=1;i<=n;i++){
if(!vis[i]){
memset(dis,-1,sizeof(dis));
dis[i]=0;
_tarjan(i);
}
}
for(i=0;i<c;i++)
if(ans[i]==-1) printf("Not connected
");
else printf("%d
",ans[i]);
}
return 0;
}